组合总和

题意

给定无重复元素的整数数组 candidates 和目标整数 target，找出所有和为 target 的组合。同一个候选数可以无限重复选取。不同组合以至少一个数字的选取数量不同来区分。

思路

最直接的思路是枚举每个候选数的使用次数，形成一条选择序列后检查总和是否等于 target：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42// brute.cpp：小数据暴力解，递归枚举每个候选数使用 0、1、2……次。
#include <bits/stdc++.h>
using namespace std;

int n, target;
int c[15];
int cnt[15]; // cnt[i] 表示候选 c[i] 被选了几次
vector<vector<int>> ans;

void dfs(int i, int sum) {
    if (sum > target)
        return;
    if (i == n) {
        if (sum == target) {
            vector<int> cur;
            for (int j = 0; j < n; j++)
                for (int k = 0; k < cnt[j]; k++)
                    cur.push_back(c[j]);
            ans.push_back(cur);
        }
        return;
    }
    // 枚举 c[i] 选 0, 1, 2, ... 次，直到超出 target
    for (cnt[i] = 0; sum + cnt[i] * c[i] <= target; cnt[i]++) {
        dfs(i + 1, sum + cnt[i] * c[i]);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> target;
    for (int i = 0; i < n; i++)
        cin >> c[i];
    dfs(0, 0);
    for (auto &v : ans) {
        for (int x : v)
            cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

这个暴力用 cnt[i] 记录每个候选数的选取次数，递归到所有候选数决定完毕后再检查总和。它在小数据上可靠，但当候选数多或目标值大时分支爆炸。

优化的关键是：在递归过程中直接维护剩余值 left，若 left < 0 立即剪枝返回；同时用"选/不选"的二元分支结构——dfs(i+1, left) 表示跳过 candidates[i]，dfs(i, left - candidates[i]) 表示使用一次 candidates[i] 且不推进下标（允许重复使用）。

用起始下标而非从 0 开始，保证组合内部有序，避免产生重复组合（如 [2,3] 和 [3,2]）。排序候选数后还可以进一步剪枝：若 left < candidates[i]，后续更大的候选数也无法命中，直接停止。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int> &candidates, int target) {
        vector<vector<int>> ans;
        vector<int> cur;
        function<void(int, int)> dfs = [&](int i, int left) {
            if (left == 0) {
                ans.push_back(cur);
                return;
            }
            if (i == (int)candidates.size() || left < 0)
                return;
            dfs(i + 1, left);
            cur.push_back(candidates[i]);
            dfs(i, left - candidates[i]);
            cur.pop_back();
        };
        dfs(0, target);
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, t;
    cin >> n >> t;
    vector<int> a(n);
    for (int &x : a)
        cin >> x;
    for (auto &v : Solution().combinationSum(a, t)) {
        for (int x : v)
            cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32#!/usr/bin/env python3
from typing import List


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

        def dfs(i, left):
            if left == 0:
                ans.append(cur[:])
                return
            if i == len(candidates) or left < 0:
                return
            dfs(i + 1, left)
            cur.append(candidates[i])
            dfs(i, left - candidates[i])
            cur.pop()

        dfs(0, target)
        return ans


def main():
    n, t = map(int, input().split())
    a = list(map(int, input().split()))
    for v in Solution().combinationSum(a, t):
        print(*v)


if __name__ == "__main__":
    main()

复杂度

时间复杂度：取决于方案数，最坏情况所有组合都合法时为 $O(2^t)$ ，实际远小于此。
空间复杂度： $O(k)$ ，递归栈深度最多等于候选数个数，cur 长度最多等于组合长度。

总结

组合枚举题的关键是避免重复组合。用起始下标 i 控制"只往后选"，同一候选数可以重复使用时不推进下标（dfs(i, ...)），不再使用时推进（dfs(i+1, ...)）。剪枝条件 left < 0 和排序后的 left < candidates[i] 能显著减少无效递归。

目录

题意

思路

代码

复杂度

总结