组合总和 II 图解题解

这道题到底在问什么

candidates

[10,1,2,7,6,1,5], target=8

输出

[[1,1,6],[1,2,5],[1,7],[2,6]]

最优解：一步一步想明白

1. 3关键不是背模板，而是看懂为什么这题适合回溯 · 去重。
2. 4排序 → [1,1,2,5,6,7,10]，相同数字相邻。target=8，每选一个数就从 remain 里减掉，remain 减到 0 即一个答案。每个数只用一次 → 递归传 i+1。
3. 5选下标 0 的 1 → remain = 8 − 1 = 7。
4. 6下一层(i+1)选下标 1 的 1 —— 它在更深层，不是同层重复，可以选 → remain 6。
5. 7选下标 4 的 6 → remain 6 − 6 = 0 → 收集 [1,1,6]！
6. 8撤销 6 回到 [1,1](remain 6)，下一个候选是下标5的 7：7 ＞ remain 6。排序后后面只会更大 → 直接 break 剪枝，不再往下试。
7. 9下标0的 1 这条大分支全部走完，回到根。本想从下标1的 1 再开同样的分支，但它和同层下标0的 1 值相同 → 跳过（i ＞ start 且 nums[i]==nums[i−1]），否则会重复生成一整批 [1,…]。
8. 10换从下标2的 2 开分支：2 → 6 → remain 0 → 收集 [2,6]。（同样方式，途中还找到 [1,2,5]、[1,7]）
9. 11完整搜索得 4 个和为 8 的不重复组合：[[1,1,6],[1,2,5],[1,7],[2,6]]。靠「同层去重」防重复、「候选＞remain 就 break」剪枝。
10. 14把这句话记住，下次遇到同类题，就能更快选出方向。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def combinationSum2(self, candidates, target):
        candidates.sort()
        ans = []
        def backtrack(start, remain, path):
            if remain == 0:
                ans.append(path[:]); return
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue                       # 同层去重
                if candidates[i] > remain:
                    break                          # 排序后剪枝
                path.append(candidates[i])
                backtrack(i + 1, remain - candidates[i], path)   # i+1: 只用一次
                path.pop()
        backtrack(0, target, [])
        return ans

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    void backtrack(vector<int>& c, int start, int remain) {
        if (remain == 0) { ans.push_back(path); return; }
        for (int i = start; i < c.size(); i++) {
            if (i > start && c[i] == c[i-1]) continue;  // 同层去重
            if (c[i] > remain) break;                   // 排序后剪枝
            path.push_back(c[i]);
            backtrack(c, i + 1, remain - c[i]);         // i+1: 只用一次
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, 0, target);
        return ans;
    }
};

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    void backtrack(int[] c, int start, int remain) {
        if (remain == 0) { ans.add(new ArrayList<>(path)); return; }
        for (int i = start; i < c.length; i++) {
            if (i > start && c[i] == c[i-1]) continue;  // 同层去重
            if (c[i] > remain) break;                   // 排序后剪枝
            path.add(c[i]);
            backtrack(c, i + 1, remain - c[i]);         // i+1: 只用一次
            path.remove(path.size() - 1);
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates, 0, target);
        return ans;
    }
}

# 组合总和II骨架 · 同层去重 + 剪枝
candidates.sort()
def backtrack(start, remain, path):
    if remain == 0: 收集 path; return
    for i in range(start, n):
        if i > start and c[i] == c[i-1]: continue   # ① 同层去重
        if c[i] > remain: break                     # ② 排序后剪枝
        path.append(c[i]); backtrack(i+1, remain-c[i], path); path.pop()  # i+1 只用一次

复杂度

面试官可能追问