39. 组合总和

难度：🟡 Medium | 标签：回溯 | 状态：⬜ LeetCode 链接

思路

每个元素可重复用 → 递归时 i 不前进（依然从 i 开始）。 target 减到 0 收集；减到负则剪枝。

代码

class Solution {
    vector<vector<int>> res;
    vector<int> path;
    void dfs(vector<int>& a, int target, int start) {
        if (target == 0) { res.push_back(path); return; }
        for (int i = start; i < (int)a.size(); ++i) {
            if (a[i] > target) continue;     // 排序后可 break
            path.push_back(a[i]);
            dfs(a, target - a[i], i);        // i 不变，可重复用
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& a, int target) {
        sort(a.begin(), a.end());
        dfs(a, target, 0);
        return res;
    }
};

复杂度

• 时间最差 O(N^(target/min))，回溯无紧界

易错 / 回顾

• 排序后 a[i] > target 可直接 break
• 用 start 防重复组合（如 [2,2,3] 和 [3,2,2]）
• 元素不可重用版本（40）：dfs(..., i + 1) 且同层去重