Medium

题目描述

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

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

示例 3：

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

提示：

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

解题思路

这道题是经典的回溯算法问题。我们需要找出所有可能的数字组合，使得它们的和等于目标值。

主要思路：

  1. 回溯法（推荐）：使用递归的方式，对每个候选数字，有两种选择：

    • 选择当前数字，目标值减去该数字，继续递归
    • 不选择当前数字，移动到下一个候选数字

  2. 关键点处理：

    • 由于每个数字可以重复使用，在选择某个数字后，下次递归仍从该位置开始
    • 使用 start 参数避免重复组合（如 [2,3] 和 [3,2]）
    • 当目标值为 0 时，找到一个有效组合
    • 当目标值小于 0 时，剪枝返回

  3. 优化策略：

    • 可以先对数组排序，当遇到比剩余目标值大的数字时提前剪枝
    • 使用引用传递减少内存开销

算法流程：从第一个候选数字开始，递归尝试所有可能的组合，通过回溯撤销选择，直到遍历完所有可能性。

代码实现

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> combination;
        backtrack(candidates, target, 0, combination, result);
        return result;
    }
    
private:
    void backtrack(vector<int>& candidates, int target, int start, 
                   vector<int>& combination, vector<vector<int>>& result) {
        if (target == 0) {
            result.push_back(combination);
            return;
        }
        
        for (int i = start; i < candidates.size(); i++) {
            if (candidates[i] > target) continue;
            
            combination.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i, combination, result);
            combination.pop_back();
        }
    }
};

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        
        def backtrack(start, combination, remaining):
            if remaining == 0:
                result.append(combination[:])
                return
            
            for i in range(start, len(candidates)):
                if candidates[i] > remaining:
                    continue
                
                combination.append(candidates[i])
                backtrack(i, combination, remaining - candidates[i])
                combination.pop()
        
        backtrack(0, [], target)
        return result

public class Solution {
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        var result = new List<IList<int>>();
        var combination = new List<int>();
        Backtrack(candidates, target, 0, combination, result);
        return result;
    }
    
    private void Backtrack(int[] candidates, int target, int start, 
                          List<int> combination, IList<IList<int>> result) {
        if (target == 0) {
            result.Add(new List<int>(combination));
            return;
        }
        
        for (int i = start; i < candidates.Length; i++) {
            if (candidates[i] > target) continue;
            
            combination.Add(candidates[i]);
            Backtrack(candidates, target - candidates[i], i, combination, result);
            combination.RemoveAt(combination.Count - 1);
        }
    }
}

var combinationSum = function(candidates, target) {
    const result = [];
    
    function backtrack(start, currentCombination, remainingTarget) {
        if (remainingTarget === 0) {
            result.push([...currentCombination]);
            return;
        }
        
        if (remainingTarget < 0) {
            return;
        }
        
        for (let i = start; i < candidates.length; i++) {
            currentCombination.push(candidates[i]);
            backtrack(i, currentCombination, remainingTarget - candidates[i]);
            currentCombination.pop();
        }
    }
    
    backtrack(0, [], target);
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(N^(T/M))，其中 N 是候选数组长度，T 是目标值，M 是数组中的最小值。最坏情况下需要探索所有可能的组合
空间复杂度O(T/M)，递归深度最多为 T/M（使用最小值组成目标值的情况），不考虑结果存储空间

相关题目