39. 组合总和

题目描述

输入一个元素互不相同的整数数组 candidates 和整数 target。

从 candidates 中挑选数字，同一个数可以被选任意多次，使所选数字之和等于 target。只要有一个数被选的次数不同，就算不同的组合；选的先后顺序不影响组合是否相同。

返回所有不同的组合，顺序不限。没有则返回空数组。题目保证组合数少于 150 个。

示例 1

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

解释：2 + 2 + 3 = 7，其中 2 用了两次；7 本身也等于 7。只有这两种。

示例 2

输入：candidates = [2,3,5], target = 8
输出：[[2,2,2,2],[2,3,3],[3,5]]

解释：2+2+2+2、2+3+3、3+5 都等于 8。

示例 3

输入：candidates = [2], target = 1
输出：[]

解释：最小的数是 2，凑不出 1。

数据范围

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 中的元素互不相同。
1 <= target <= 40

解题思路：排序 + 回溯剪枝

排序后回溯，递归传入当前索引。

为什么正确

组合按非递减索引生成且不超目标。

复杂度分析

时间 O(S)，额外空间 O(target)。

易错点

注意边界条件并在回溯或弹出后恢复状态。

参考代码

Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。

class Solution:
 def combinationSum(self,a,t):
  a.sort();out=[];p=[]
  def f(s,r):
   if r==0:out.append(p[:]);return
   for i in range(s,len(a)):
    if a[i]>r:break
    p.append(a[i]);f(i,r-a[i]);p.pop()
  f(0,t);return out

class Solution {
    private int[] a;
    private List<List<Integer>> out;
    private List<Integer> p;

    public List<List<Integer>> combinationSum(int[] a, int t) {
        Arrays.sort(a); this.a = a; out = new ArrayList<>(); p = new ArrayList<>();
        f(0, t); return out;
    }

    private void f(int s, int r) {
        if (r == 0) { out.add(new ArrayList<>(p)); return; }
        for (int i = s; i < a.length; i++) {
            if (a[i] > r) break;
            p.add(a[i]); f(i, r - a[i]); p.remove(p.size() - 1);
        }
    }
}

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& a, int t) {
        sort(a.begin(), a.end()); vector<vector<int>> out; vector<int> p;
        function<void(int, int)> f = [&](int s, int r) {
            if (r == 0) { out.push_back(p); return; }
            for (int i = s; i < (int)a.size(); i++) {
                if (a[i] > r) break;
                p.push_back(a[i]); f(i, r - a[i]); p.pop_back();
            }
        };
        f(0, t); return out;
    }
};

func combinationSum(a []int, t int) [][]int {
	sort.Ints(a); out := [][]int{}; p := []int{}
	var f func(s, r int)
	f = func(s, r int) {
		if r == 0 {
			out = append(out, append([]int(nil), p...))
			return
		}
		for i := s; i < len(a); i++ {
			if a[i] > r {
				break
			}
			p = append(p, a[i]); f(i, r-a[i]); p = p[:len(p)-1]
		}
	}
	f(0, t); return out
}

var combinationSum = function(a, t) {
    a.sort((x, y) => x - y); const out = [], p = [];
    const f = (s, r) => {
        if (r === 0) { out.push([...p]); return; }
        for (let i = s; i < a.length; i++) {
            if (a[i] > r) break;
            p.push(a[i]); f(i, r - a[i]); p.pop();
        }
    };
    f(0, t); return out;
};

function combinationSum(a: number[], t: number): number[][] {
    a.sort((x, y) => x - y); const out: number[][] = [], p: number[] = [];
    const f = (s: number, r: number): void => {
        if (r === 0) { out.push([...p]); return; }
        for (let i = s; i < a.length; i++) {
            if (a[i] > r) break;
            p.push(a[i]); f(i, r - a[i]); p.pop();
        }
    };
    f(0, t); return out;
}

载入编辑器，自己跑一遍 →

其他解法

回溯自顶向下逐条搜索，只在内存里保存一条路径，内存省；动态规划自底向上为每个中间和保存所有组合，思路与完全背包计数一致，但需要存储大量中间结果。

解法 2：完全背包式动态规划构造组合时间 O(n·target + S)，空间 O(S)

dp[s] 保存和为 s 的所有组合，初始 dp[0] = [[]]。外层按升序枚举候选数 c，内层 s 从 c 到 target 递增，把 dp[s-c] 中每个组合末尾追加 c 放入 dp[s]。由于 s 递增，同一个 c 可以重复使用；由于候选数在外层，每个组合内的数字都按候选顺序排列，不会出现同一组合的不同排列。

把回溯改写成自底向上的完全背包，帮助理解“外层物品、内层容量”为什么能求组合而不是排列。缺点是要保存所有中间和的全部组合，空间远大于回溯只维护一条路径。S 表示所有可行组合的总长度。

class Solution:
    def combinationSum(self, candidates, target):
        dp = [[] for _ in range(target + 1)]
        dp[0] = [[]]
        for c in sorted(candidates):
            for s in range(c, target + 1):
                for comb in dp[s - c]:
                    dp[s].append(comb + [c])
        return dp[target]

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<List<Integer>>> dp = new ArrayList<>();
        for (int s = 0; s <= target; s++) dp.add(new ArrayList<>());
        dp.get(0).add(new ArrayList<>());
        Arrays.sort(candidates);
        for (int c : candidates) {
            for (int s = c; s <= target; s++) {
                for (List<Integer> comb : dp.get(s - c)) {
                    List<Integer> nxt = new ArrayList<>(comb);
                    nxt.add(c);
                    dp.get(s).add(nxt);
                }
            }
        }
        return dp.get(target);
    }
}

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<vector<int>>> dp(target + 1);
        dp[0].push_back({});
        sort(candidates.begin(), candidates.end());
        for (int c : candidates) {
            for (int s = c; s <= target; s++) {
                for (const auto& comb : dp[s - c]) {
                    vector<int> nxt = comb;
                    nxt.push_back(c);
                    dp[s].push_back(nxt);
                }
            }
        }
        return dp[target];
    }
};

func combinationSum(candidates []int, target int) [][]int {
	dp := make([][][]int, target+1)
	dp[0] = [][]int{{}}
	sort.Ints(candidates)
	for _, c := range candidates {
		for s := c; s <= target; s++ {
			for _, comb := range dp[s-c] {
				nxt := append(append([]int{}, comb...), c)
				dp[s] = append(dp[s], nxt)
			}
		}
	}
	if dp[target] == nil {
		return [][]int{}
	}
	return dp[target]
}

var combinationSum = function(candidates, target) {
    const dp = Array.from({length: target + 1}, () => []);
    dp[0].push([]);
    candidates.sort((a, b) => a - b);
    for (const c of candidates) {
        for (let s = c; s <= target; s++) {
            for (const comb of dp[s - c]) dp[s].push([...comb, c]);
        }
    }
    return dp[target];
};

function combinationSum(candidates: number[], target: number): number[][] {
    const dp: number[][][] = Array.from({length: target + 1}, () => []);
    dp[0].push([]);
    candidates.sort((a, b) => a - b);
    for (const c of candidates) {
        for (let s = c; s <= target; s++) {
            for (const comb of dp[s - c]) dp[s].push([...comb, c]);
        }
    }
    return dp[target];
}

回溯专题的其他题目

查看回溯全部题目 →