组合总和 图解题解

这道题和普通组合题差在哪

给定候选数组和目标值 target，找出所有和恰好等于 target 的组合。它有两个特殊设定：其一，同一个数可以重复选任意次——示例 candidates 为 [2,3,6,7]、target 为 7 时，答案是 [2,2,3] 和 [7]，前者把 2 用了两次；其二，组合之间不许重复，[2,2,3] 和 [3,2,2] 只能算一个。一边允许「元素重复」，一边禁止「组合重复」，解法必须同时兼顾这两条，这正是本题的看点。

递归传 i 而不是 i + 1 是题眼

回溯每选中下标 i 的数，下一层递归的起点仍然传 i——就这一个字符的差别，决定了能否重复选。传 i，下一层还能再选到自己，[2,2,3] 才凑得出来；改传 i + 1，就退化成每个数只能用一次的 LC40 组合总和 II，含重复元素的解会整批丢失。同时用 remain 记剩余目标，每层减去所选的数，减到 0 说明恰好凑满，把当前 path 的副本收进结果并返回。

start 下标怎么保证组合不重复

防止 [2,2,3] 和 [3,2,2] 被当成两个答案的手法，与子集类问题同源：每层只从 start 往后选，绝不回头选前面的下标。于是任何一条路径里元素的下标非降，每个组合唯一对应「按下标顺序选取」这一种走法。换个角度说，重复组合的根源是同一批数换个顺序再来一遍，而 start 直接封死了回头路——去重不靠事后比对结果集，而是在生成阶段就杜绝。

排序之后为什么敢 break 整层

剪枝的依据是升序：一旦当前候选 candidates[i] 已经大于 remain，选它必然超出目标；而排序保证它后面的候选只会更大，同样全部超标——所以可以 break 直接结束这一层循环，而不是 continue 逐个再试。没有排序就没有「后面更大」的保证，只能 continue，会白白探索大量注定失败的分支。这一步不改变答案集合，只砍掉无效搜索，是回溯题「先排序再剪枝」的典型配合。

复杂度与常见翻车点

搜索树规模约为 O(N^(T/M))：N 是候选个数，T 是 target，M 是最小候选值——最坏情况下每层至多 N 个分支、深度可达 T/M（一直选最小的数）。递归深度即 path 的最长长度，空间 O(T/M)。三个高频错误：递归传成 i + 1，漏掉需要重复选的解；每层都从头开始选，产生换序重复的组合；不剪枝、只靠递归到底再判和，分支爆炸容易超时。最后别忘了收集答案时存 path 的副本，而不是引用本身。

Python

def combinationSum(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 candidates[i] > remain: break   # 剪枝
            path.append(candidates[i])
            bt(i, remain - candidates[i])     # 传 i: 可重复选
            path.pop()                        # 回溯
    bt(0, target)
    return res

C++

class Solution {
public:
    vector<vector<int>> res; vector<int> path;
    vector<vector<int>> combinationSum(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(c[i] > remain) break;          // 剪枝
            path.push_back(c[i]);
            bt(c, i, remain - c[i]);          // 传 i: 可重复选
            path.pop_back();                  // 回溯
        }
    }
};

Java

public class Main {
    static List<List<Integer>> res = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();
    public static List<List<Integer>> combinationSum(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(c[i] > remain) break;          // 剪枝
            path.add(c[i]);
            bt(c, i, remain - c[i]);          // 传 i: 可重复选
            path.remove(path.size() - 1);     // 回溯
        }
    }
}