39. 组合总和

力扣题目链接 (opens new window)

题目描述

给定一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为 target 的所有不同组合，并以列表形式返回。candidates 中的同一个数字可以无限制重复选取。

示例 1：

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

示例 2：

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

思路

本题和组合有什么区别？它没有数量要求，同一个元素还能无限重复选取，但路径总和必须等于 target。

既然同一个元素可以重复选，递归进入下一层时为什么还需要 startIndex？因为结果是组合而不是排列，[2,2,3] 和 [2,3,2] 不能重复出现。startIndex 保证后续只从当前元素及其右侧继续选。

回溯三部曲：

1. 参数包含当前总和 sum 和本层起点 startIndex。
2. sum == target 时收集结果；超过 target 的分支不再搜索。
3. 选择 candidates[i] 后，下一层仍传入 i，而不是 i + 1，表示当前数字可以重复选取。

如何剪枝？先将数组排序。如果 sum + candidates[i] > target，后面的数只会更大，本层循环可以直接结束。

求和问题中，排序之后加剪枝是常见套路。

模拟过程

以 candidates = [2,3,6,7], target = 7 为例。先选择 2，下一层仍从 2 开始，所以可以得到路径 [2,2,3]；不能从头重新选择，否则会产生 [2,3,2] 这样的重复组合。

排序后，当当前总和再加上 candidates[i] 已经大于 7，就直接结束本层遍历，剪掉后面更大的候选数。

解题代码

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.push_back(path);
            return;
        }
        for (int i = startIndex;
             i < candidates.size() && sum + candidates[i] <= target; ++i) {
            path.push_back(candidates[i]);
            backtracking(candidates, target, sum + candidates[i], i); // i 表示可以重复选
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        result.clear(); path.clear();
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return result;
    }
};

复杂度分析

• 时间复杂度：最坏为指数级，实际搜索量取决于 target、候选数和剪枝效果。
• 空间复杂度：O(target / m)，其中 m 是最小候选数，表示递归路径的最大深度；不计返回结果。

其他语言

Python3

class Solution:
    def combinationSum(self, candidates, target):
        candidates.sort()
        result, path = [], []
        def backtracking(start, total):
            if total == target:
                result.append(path[:]); return
            for i in range(start, len(candidates)):
                if total + candidates[i] > target: break
                path.append(candidates[i])
                backtracking(i, total + candidates[i])
                path.pop()
        backtracking(0, 0)
        return result

Java

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates); backtracking(candidates, target, 0, 0); return result;
    }
    void backtracking(int[] nums, int target, int sum, int start) {
        if (sum == target) { result.add(new ArrayList<>(path)); return; }
        for (int i = start; i < nums.length && sum + nums[i] <= target; i++) {
            path.add(nums[i]); backtracking(nums, target, sum + nums[i], i); path.removeLast();
        }
    }
}

Go

func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates)
    result, path := [][]int{}, []int{}
    var dfs func(int, int)
    dfs = func(start, remain int) {
        if remain == 0 { result = append(result, append([]int{}, path...)); return }
        for i := start; i < len(candidates) && candidates[i] <= remain; i++ {
            path = append(path, candidates[i]); dfs(i, remain-candidates[i]); path = path[:len(path)-1]
        }
    }
    dfs(0, target); return result
}

JS

var combinationSum = function(candidates, target) {
    candidates.sort((a, b) => a - b);
    const result = [], path = [];
    function backtracking(start, sum) {
        if (sum === target) { result.push([...path]); return; }
        for (let i = start; i < candidates.length && sum + candidates[i] <= target; i++) {
            path.push(candidates[i]); backtracking(i, sum + candidates[i]); path.pop();
        }
    }
    backtracking(0, 0); return result;
};

与代码随想录联系

代码随想录的39.组合总和对“元素可以重复选择”和“组合不能重复”这两个关键点有完整推导。本题也可以和77.组合对比：77 题递归传 i + 1，本题递归传 i。