组合总和 II 图解题解

这道题到底在问什么

candidates

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

target

8

输出

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

最优解：一步一步想明白

1. 3记住这三件事：传 i+1（只用一次）→ 同层跳重（去重）→ 超额就剪。下面每一帧就是其中一个动作。
2. 4这一层从下标 0 的 1 往下钻：把它加进 path，剩余从 8 减到 7。
3. 5path → [1]。进入下一层从下标 1 继续——传 i+1，所以每个数只用一次。
4. 6这一层从下标 1 的 1 往下钻：把它加进 path，剩余从 7 减到 6。
5. 7path → [1,1]。进入下一层从下标 2 继续——传 i+1，所以每个数只用一次。
6. 8这一层从下标 2 的 2 往下钻：把它加进 path，剩余从 6 减到 4。
7. 9path → [1,1,2]。进入下一层从下标 3 继续——传 i+1，所以每个数只用一次。
8. 10剩余只要凑 4，但下标 3 的 5 已经更大——再选必然超 8，升序下它后面的更大，整层一起放弃，画 ✗。
9. 11这条分支走完，撤销 2（path → [1,1]），回到上一层换下一个候选。
10. 12这一层从下标 3 的 5 往下钻：把它加进 path，剩余从 6 减到 1。
11. 13path → [1,1,5]。进入下一层从下标 4 继续——传 i+1，所以每个数只用一次。
12. 14剩余只要凑 1，但下标 4 的 6 已经更大——再选必然超 8，升序下它后面的更大，整层一起放弃，画 ✗。
13. 15这条分支走完，撤销 5（path → [1,1]），回到上一层换下一个候选。
14. 16这一层从下标 4 的 6 往下钻：把它加进 path，剩余从 6 减到 0。
15. 17path → [1,1,6]。进入下一层从下标 5 继续——传 i+1，所以每个数只用一次。
16. 18剩余 = 0，path [1,1,6] 之和正好 = 8！收进结果。这是一条合法组合。
17. 19这条分支走完，撤销 6（path → [1,1]），回到上一层换下一个候选。
18. 20剩余只要凑 6，但下标 5 的 7 已经更大——再选必然超 8，升序下它后面的更大，整层一起放弃，画 ✗。
19. 21这条分支走完，撤销 1（path → [1]），回到上一层换下一个候选。
20. 22这一层从下标 2 的 2 往下钻：把它加进 path，剩余从 7 减到 5。
21. 23path → [1,2]。进入下一层从下标 3 继续——传 i+1，所以每个数只用一次。
22. 24这一层从下标 3 的 5 往下钻：把它加进 path，剩余从 5 减到 0。
23. 25path → [1,2,5]。进入下一层从下标 4 继续——传 i+1，所以每个数只用一次。
24. 26剩余 = 0，path [1,2,5] 之和正好 = 8！收进结果。这是一条合法组合。
25. 27这条分支走完，撤销 5（path → [1,2]），回到上一层换下一个候选。
26. 28剩余只要凑 5，但下标 4 的 6 已经更大——再选必然超 8，升序下它后面的更大，整层一起放弃，画 ✗。
27. 29这条分支走完，撤销 2（path → [1]），回到上一层换下一个候选。
28. 30这一层从下标 3 的 5 往下钻：把它加进 path，剩余从 7 减到 2。
29. 31path → [1,5]。进入下一层从下标 4 继续——传 i+1，所以每个数只用一次。
30. 32剩余只要凑 2，但下标 4 的 6 已经更大——再选必然超 8，升序下它后面的更大，整层一起放弃，画 ✗。
31. 33这条分支走完，撤销 5（path → [1]），回到上一层换下一个候选。
32. 34这一层从下标 4 的 6 往下钻：把它加进 path，剩余从 7 减到 1。
33. 35path → [1,6]。进入下一层从下标 5 继续——传 i+1，所以每个数只用一次。
34. 36剩余只要凑 1，但下标 5 的 7 已经更大——再选必然超 8，升序下它后面的更大，整层一起放弃，画 ✗。
35. 37这条分支走完，撤销 6（path → [1]），回到上一层换下一个候选。
36. 38这一层从下标 5 的 7 往下钻：把它加进 path，剩余从 7 减到 0。
37. 39path → [1,7]。进入下一层从下标 6 继续——传 i+1，所以每个数只用一次。
38. 40剩余 = 0，path [1,7] 之和正好 = 8！收进结果。这是一条合法组合。
39. 41这条分支走完，撤销 7（path → [1]），回到上一层换下一个候选。
40. 42剩余只要凑 7，但下标 6 的 10 已经更大——再选必然超 8，升序下它后面的更大，整层一起放弃，画 ✗。
41. 43这条分支走完，撤销 1（path → []），回到上一层换下一个候选。
42. 44下标 1 的 1 和同层前一个下标 0 的 1 相同，这一层已经从前一个 1 开过分支了，再选会产出重复组合 → 画 ✗ 剪掉。
43. 45这一层从下标 2 的 2 往下钻：把它加进 path，剩余从 8 减到 6。
44. 46path → [2]。进入下一层从下标 3 继续——传 i+1，所以每个数只用一次。
45. 47这一层从下标 3 的 5 往下钻：把它加进 path，剩余从 6 减到 1。
46. 48path → [2,5]。进入下一层从下标 4 继续——传 i+1，所以每个数只用一次。
47. 49剩余只要凑 1，但下标 4 的 6 已经更大——再选必然超 8，升序下它后面的更大，整层一起放弃，画 ✗。
48. 50这条分支走完，撤销 5（path → [2]），回到上一层换下一个候选。
49. 51这一层从下标 4 的 6 往下钻：把它加进 path，剩余从 6 减到 0。
50. 52path → [2,6]。进入下一层从下标 5 继续——传 i+1，所以每个数只用一次。
51. 53剩余 = 0，path [2,6] 之和正好 = 8！收进结果。这是一条合法组合。
52. 54这条分支走完，撤销 6（path → [2]），回到上一层换下一个候选。
53. 55剩余只要凑 6，但下标 5 的 7 已经更大——再选必然超 8，升序下它后面的更大，整层一起放弃，画 ✗。
54. 56这条分支走完，撤销 2（path → []），回到上一层换下一个候选。
55. 57这一层从下标 3 的 5 往下钻：把它加进 path，剩余从 8 减到 3。
56. 58path → [5]。进入下一层从下标 4 继续——传 i+1，所以每个数只用一次。
57. 59剩余只要凑 3，但下标 4 的 6 已经更大——再选必然超 8，升序下它后面的更大，整层一起放弃，画 ✗。
58. 60这条分支走完，撤销 5（path → []），回到上一层换下一个候选。
59. 61这一层从下标 4 的 6 往下钻：把它加进 path，剩余从 8 减到 2。
60. 62path → [6]。进入下一层从下标 5 继续——传 i+1，所以每个数只用一次。
61. 63剩余只要凑 2，但下标 5 的 7 已经更大——再选必然超 8，升序下它后面的更大，整层一起放弃，画 ✗。
62. 64这条分支走完，撤销 6（path → []），回到上一层换下一个候选。
63. 65这一层从下标 5 的 7 往下钻：把它加进 path，剩余从 8 减到 1。
64. 66path → [7]。进入下一层从下标 6 继续——传 i+1，所以每个数只用一次。
65. 67剩余只要凑 1，但下标 6 的 10 已经更大——再选必然超 8，升序下它后面的更大，整层一起放弃，画 ✗。
66. 68这条分支走完，撤销 7（path → []），回到上一层换下一个候选。
67. 69搜索结束。所有「每个数只用一次、同层不重、不超 8」的路径都试过了，收集到 4 条组合：[[1,1,6],[1,2,5],[1,7],[2,6]]。

⚠️ 容易写错的地方

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

def combinationSum2(candidates, target):
    candidates.sort()                    # 排序: 相同数字相邻 + 便于剪枝
    res, path = [], []
    def bt(start, remain):
        if remain == 0:
            res.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                    # 超 target 剪枝
            path.append(candidates[i])
            bt(i + 1, remain - candidates[i])  # 传 i+1: 每个数只用一次
            path.pop()                   # 回溯撤销
    bt(0, target)
    return res

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

public class Main {
    static List<List<Integer>> res = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();
    public static List<List<Integer>> combinationSum2(int[] c, int target){
        Arrays.sort(c);                  // 排序: 相同数字相邻 + 便于剪枝
        bt(c, 0, target);
        return res;
    }
    static void bt(int[] c, int start, int remain){
        if(remain == 0){ res.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;                   // 超 target 剪枝
            path.add(c[i]);
            bt(c, i + 1, remain - c[i]);               // 传 i+1: 每个数只用一次
            path.remove(path.size() - 1);              // 回溯撤销
        }
    }
}

复杂度

面试官可能追问