题目链接 · 灵神原题解（署名来源）

方法一：选或不选

前置题目：78. 子集

视频讲解：回溯算法套路①子集型回溯【基础算法精讲 14】

用 $\mathit{\text{dfs}}(i,\mathit{\text{left}})$ 来回溯，设当前枚举到 $\mathit{\text{candidates}}[i]$，剩余要选的元素之和为 $\mathit{\text{left}}$，按照选或不选分类讨论：

• 不选 $\mathit{\text{candidates}}[i]$：递归到 $\mathit{\text{dfs}}(i+1,\mathit{\text{left}})$。
• 选 $\mathit{\text{candidates}}[i]$：递归到 $\mathit{\text{dfs}}(i,\mathit{\text{left}}-\mathit{\text{candidates}}[i])$。注意 $i$ 不变，表示在下次递归中可以继续选 $\mathit{\text{candidates}}[i]$。

注：这个思路类似 完全背包。

如果递归中发现 $\mathit{\text{left}}=0$ 则说明找到了一个合法组合，复制一份 $\mathit{\text{path}}$ 加入答案。

递归边界：如果 $i=n$ 或者 $\mathit{\text{left}}<0$ 则返回。

递归入口：$\mathit{\text{dfs}}(0,\mathit{\text{target}})$。

Python 解法1

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        ans = []
        path = []

        def dfs(i: int, left: int) -> None:
            if left == 0:
                # 找到一个合法组合
                ans.append(path.copy())
                return

            if i == len(candidates) or left < 0:
                return

            # 不选
            dfs(i + 1, left)

            # 选
            path.append(candidates[i])
            dfs(i, left - candidates[i])
            path.pop()  # 恢复现场

        dfs(0, target)
        return ans

C++ 解法1

// C++ 版待补充

C++ 解法2

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> path;

        auto dfs = [&](this auto&& dfs, int i, int left) {
            if (left == 0) {
                // 找到一个合法组合
                ans.push_back(path);
                return;
            }

            if (i == candidates.size() || left < 0) {
                return;
            }

            // 不选
            dfs(i + 1, left);

            // 选
            path.push_back(candidates[i]);
            dfs(i, left - candidates[i]);
            path.pop_back(); // 恢复现场
        };

        dfs(0, target);
        return ans;
    }
};

剪枝优化

把 $\mathit{\text{candidates}}$ 从小到大排序，如果递归中发现 $\mathit{\text{left}}<\mathit{\text{candidates}}[i]$，由于后面的数字只会更大，所以无法把 $\mathit{\text{left}}$ 减小到 $0$，可以直接返回。

Python 解法3

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []
        path = []

        def dfs(i: int, left: int) -> None:
            if left == 0:
                # 找到一个合法组合
                ans.append(path.copy())
                return

            if i == len(candidates) or left < candidates[i]:
                return

            # 不选
            dfs(i + 1, left)

            # 选
            path.append(candidates[i])
            dfs(i, left - candidates[i])
            path.pop()  # 恢复现场

        dfs(0, target)
        return ans

C++ 解法3

// C++ 版待补充

C++ 解法4

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        ranges::sort(candidates);
        vector<vector<int>> ans;
        vector<int> path;

        auto dfs = [&](this auto&& dfs, int i, int left) {
            if (left == 0) {
                // 找到一个合法组合
                ans.push_back(path);
                return;
            }

            if (i == candidates.size() || left < candidates[i]) {
                return;
            }

            // 不选
            dfs(i + 1, left);

            // 选
            path.push_back(candidates[i]);
            dfs(i, left - candidates[i]);
            path.pop_back(); // 恢复现场
        };

        dfs(0, target);
        return ans;
    }
};

复杂度分析

由如下完全背包代码可知，在 $\mathit{\text{candidates}}=[2,3,4,\cdots ,31],\mathit{\text{target}}=40$ 的极端数据下，搜索次数的上界为 $37271$。换句话说，即使题目不保证答案个数 $\le 150$，我们也能很快地找到所有答案。

Python 解法5

f = [1] + [0] * 40
for i in range(2, 32):
    for j in range(i, 41):
        f[j] += f[j - i]
print(sum(f))  # 37271

C++ 解法5

// C++ 版待补充

进一步地，计算 A002865 的前 $\mathit{\text{target}}$ 项之和，即 A000041，可得：

• 时间复杂度：$\mathcal{O}(n\log n+{\displaystyle \frac{e^{\pi \sqrt{(2/3)\cdot \mathit{\text{target}}}}}{\mathit{\text{target}}}})$，其中 $n$ 为 $\mathit{\text{candidates}}$ 的长度。如果你想用这个分式估计搜索次数的话，还要乘上 ${\displaystyle \frac{1}{4\sqrt{3}}}$ 的常系数。
• 空间复杂度：$\mathcal{O}(\mathit{\text{target}})$。返回值不计入。$\mathit{\text{path}}$ 长度和递归深度至多为 $\mathcal{O}(\mathit{\text{target}})$。

方法二：枚举选哪个

类似 视频 中的「答案视角」。同样用 $\mathit{\text{dfs}}(i,\mathit{\text{left}})$ 来回溯，设当前枚举到 $\mathit{\text{candidates}}[i]$，剩余要选的元素之和为 $\mathit{\text{left}}$，考虑枚举下个元素是谁：

• 在 $[i,n-1]$ 中枚举要填在 $\mathit{\text{path}}$ 中的元素 $\mathit{\text{candidates}}[j]$，然后递归到 $\mathit{\text{dfs}}(j,\mathit{\text{left}}-\mathit{\text{candidates}}[j])$。注意这里是递归到 $j$ 不是 $j+1$，表示 $\mathit{\text{candidates}}[j]$ 可以重复选取。

Python 解法6

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        ans = []
        path = []

        def dfs(i: int, left: int) -> None:
            if left == 0:
                # 找到一个合法组合
                ans.append(path.copy())
                return

            # 枚举选哪个
            for j in range(i, len(candidates)):
                if candidates[j] > left:  # 排序了，后面的数都太大
                    break
                path.append(candidates[j])
                dfs(j, left - candidates[j])
                path.pop()  # 恢复现场

        dfs(0, target)
        return ans

C++ 解法6

// C++ 版待补充

C++ 解法7

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        ranges::sort(candidates);
        vector<vector<int>> ans;
        vector<int> path;

        auto dfs = [&](this auto&& dfs, int i, int left) {
            if (left == 0) {
                // 找到一个合法组合
                ans.push_back(path);
                return;
            }

            // 枚举选哪个
            for (int j = i; j < candidates.size() && candidates[j] <= left; j++) {
                path.push_back(candidates[j]);
                dfs(j, left - candidates[j]);
                path.pop_back(); // 恢复现场
            }
        };

        dfs(0, target);
        return ans;
    }
};

复杂度分析

同方法一。

方法三：完全背包预处理 + 可行性剪枝

前置知识：完全背包。

例如 $\mathit{\text{candidates}}=[2,4,6,8,10]$ 都是偶数，但 $\mathit{\text{target}}=11$ 是奇数，这种情况我们在一开始递归时，就应当判断出无解，不再继续向下递归。

怎么判断？我们可以用完全背包预处理出下标在 $[0,i]$ 中的 $\mathit{\text{candidates}}$ 元素之和能否为 $j$，记作 $f[i+1][j]$。

如果递归中的 $\mathit{\text{left}}$ 不在可以组合得到的数字中，则可以直接返回。

这一做法可以保证我们是在往正确的方向一步步递归前进的。只要题目保证方案数不超过 $150$，即使 $\mathit{\text{target}}=1000$ 也能搞定。

Python 解法8

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        # 完全背包
        f = [[False] * (target + 1) for _ in range(n + 1)]
        f[0][0] = True
        for i, x in enumerate(candidates):
            for j in range(target + 1):
                f[i + 1][j] = f[i][j] or j >= x and f[i + 1][j - x]

        ans = []
        path = []

        def dfs(i: int, left: int) -> None:
            if left == 0:
                # 找到一个合法组合
                ans.append(path.copy())
                return

            # 无法用下标在 [0, i] 中的数字组合出 left
            if left < 0 or not f[i + 1][left]:
                return

            # 不选
            dfs(i - 1, left)

            # 选
            path.append(candidates[i])
            dfs(i, left - candidates[i])
            path.pop()

        # 倒着递归，这样参数符合 f 数组的定义
        dfs(n - 1, target)
        return ans

C++ 解法8

// C++ 版待补充

C++ 解法9

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int n = candidates.size();
        // 完全背包
        vector<vector<bool>> f(n + 1, vector<bool>(target + 1));
        f[0][0] = true;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= target; j++) {
                f[i + 1][j] = f[i][j] || j >= candidates[i] && f[i + 1][j - candidates[i]];
            }
        }

        vector<vector<int>> ans;
        vector<int> path;

        auto dfs = [&](this auto&& dfs, int i, int left) {
            if (left == 0) {
                // 找到一个合法组合
                ans.push_back(path);
                return;
            }

            // 无法用下标在 [0, i] 中的数字组合出 left
            if (left < 0 || !f[i + 1][left]) {
                return;
            }

            // 不选
            dfs(i - 1, left);

            // 选
            path.push_back(candidates[i]);
            dfs(i, left - candidates[i]);
            path.pop_back();
        };

        // 倒着递归，这样参数符合 f 数组的定义
        dfs(n - 1, target);
        return ans;
    }
};

• 时间复杂度：$\mathcal{O}(min({\displaystyle \frac{e^{\pi \sqrt{(2/3)\cdot \mathit{\text{target}}}}}{\mathit{\text{target}}}},k\cdot \mathit{\text{target}})+n\cdot \mathit{\text{target}})$。其中 $n$ 为 $\mathit{\text{candidates}}$ 的长度，$k\le 150$ 这是题目保证的。搜索树上至多有 $k$ 条长为 $\mathcal{O}(target)$ 的链，所以搜索树的节点个数为 $\mathcal{O}(k\cdot \mathit{\text{target}})$。计算完全背包的时间为 $\mathcal{O}(n\cdot \mathit{\text{target}})$。
• 空间复杂度：$\mathcal{O}(n\cdot \mathit{\text{target}})$。返回值不计入。

分类题单

如何科学刷题？

1. 滑动窗口与双指针（定长/不定长/单序列/双序列/三指针/分组循环）
2. 二分算法（二分答案/最小化最大值/最大化最小值/第K小）
3. 单调栈（基础/矩形面积/贡献法/最小字典序）
4. 网格图（DFS/BFS/综合应用）
5. 位运算（基础/性质/拆位/试填/恒等式/思维）
6. 图论算法（DFS/BFS/拓扑排序/最短路/最小生成树/二分图/基环树/欧拉路径）
7. 动态规划（入门/背包/状态机/划分/区间/状压/数位/数据结构优化/树形/博弈/概率期望）
8. 常用数据结构（前缀和/差分/栈/队列/堆/字典树/并查集/树状数组/线段树）
9. 数学算法（数论/组合/概率期望/博弈/计算几何/随机算法）
10. 贪心与思维（基本贪心策略/反悔/区间/字典序/数学/思维/脑筋急转弯/构造）
11. 【本题相关】链表、二叉树与回溯（前后指针/快慢指针/DFS/BFS/直径/LCA/一般树）
12. 字符串（KMP/Z函数/Manacher/字符串哈希/AC自动机/后缀数组/子序列自动机）

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府