组合总和 图解题解

这道题到底在问什么

candidates

[2, 3, 6, 7]

target

7

输出

[[2,2,3], [7]]

最优解：一步一步想明白

1. 3最直接的想法：每个候选数选几次都试一遍，再看哪些和正好等于 target。可这样既会重复(2+3 和 3+2 算两次)，又不知道什么时候该停，一路加到超了还在加。
2. 4转折：维护一个「剩余 remain」。选了某个数，remain 就减它；remain==0 说明凑齐了，记录组合；remain＜0 说明超了，剪枝回头。再用 start 下标只往后选避免重复——但因为允许重复选，递归时仍从当前数 i 开始(不前进到 i+1)。
3. 5path=[2] remain=5先选 2，path=[2]，remain = 7−2 = 5(大于 0，继续)。因为能重复，下一步仍可从 2 选起。
4. 6path=[2,2] remain=3又从 2 选起，再拿一个 2，path=[2,2]，remain = 5−2 = 3。还没到 0，继续往下。
5. 7remain=0 → 收这一层从 i=1(数字 3)选起，选 3，path=[2,2,3]，remain = 3−3 = 0！凑齐了，记录组合 [2,2,3]，然后回溯。
6. 83−6=−3 → 超了负例分支：撤销 3 回到 [2,2](remain=3)，for 前进试 6：remain = 3−6 = −3 小于 0，超了 → 剪枝、立刻返回，连递归都不进。试 7 也超，这条分支结束。
7. 9[2,3] remain=2 → 死路再撤一层回到 [2](remain=5)。「用 2」这支已试完(得到 [2,2,3])，for 前进到下一个候选 3：[2,3] remain=2，往下从 3 选起再选 3 超(2−3小于0)、选更大也超，剪枝。
8. 10[3] remain=4 → 凑不出彻底撤回到空，for 前进换 3 打头(start=1，不再回头看 2，避免重复)：[3] remain=4，再选 3 → [3,3] remain=1，此后任何候选(3/6/7)都 ＞1 → 剪；选 6 又 ＞4 → break。[3] 这支凑不出 7，撤掉。
9. 11[6] remain=1 → 凑不出再换 6 打头：[6] remain=1，但 start 锁定只能从 6 往后选，6、7 都比 1 大，remain 必为负 → 剪枝。继续前进到最后一个候选 7。
10. 12path=[7] remain=0选 7：remain = 7−7 = 0，记录 [7]。候选全试完，所有组合找齐：[[2,2,3], [7]]，和示例对上。
11. 15把「凑数」变成「剩余目标递减」，到 0 就收、超了就剪——组合总和、目标和、分割等和子集都是这套带剪枝的回溯。
12. 20把这题练到能复述后，再去同类题里迁移：先复用状态定义，再调整边界条件。

⚠️ 容易写错的地方

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

class Solution:
    def combinationSum(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)):
                x = candidates[i]
                if x > remain:
                    break
                path.append(x)
                backtrack(i, remain - x, path)
                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 (c[i] > remain) break;          // 排序后剪枝
            path.push_back(c[i]);
            backtrack(c, i, remain - c[i]);    // 传 i 不是 i+1：可重复用
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum(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 (c[i] > remain) break;          // 排序后剪枝
            path.add(c[i]);
            backtrack(c, i, remain - c[i]);    // 传 i：可重复用
            path.remove(path.size() - 1);
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtrack(candidates, 0, target);
        return ans;
    }
}

def backtrack(start, remain, path):
    if remain == 0: res.append(path[:]); return
    for i in range(start, n):
        if c[i] > remain: break        # 排序后剪枝
        path.append(c[i])
        backtrack(i, remain - c[i], path)  # 传 i 可重复 / 传 i+1 不重复
        path.pop()

void backtrack(int start, int remain, Path& path) {
    if (remain == 0) { res.push_back(path); return; }
    for (int i = start; i < n; i++) {
        if (c[i] > remain) break;          // 剪枝
        path.push_back(c[i]);
        backtrack(i, remain - c[i], path); // 传 i 可重复 / 传 i+1 不重复
        path.pop_back();
    }
}

void backtrack(int start, int remain, List<Integer> path) {
    if (remain == 0) { res.add(new ArrayList<>(path)); return; }
    for (int i = start; i < n; i++) {
        if (c[i] > remain) break;          // 剪枝
        path.add(c[i]);
        backtrack(i, remain - c[i], path); // 传 i 可重复 / 传 i+1 不重复
        path.remove(path.size()-1);
    }
}

复杂度

面试官可能追问