Medium

题目描述

给定一个候选数字集合 candidates 和一个目标数字 target，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

**注意：**解集不能包含重复的组合。

示例 1：

输入: candidates = [10,1,2,7,6,1,5], target = 8
输出: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2：

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

提示：

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

解题思路

这道题是经典的回溯算法问题，与组合总和 I 的区别在于：每个数字只能使用一次，且要去除重复组合。

核心思路：

  1. 排序：首先对数组排序，这样相同元素会相邻，便于去重
  2. 回溯搜索：使用 DFS 枚举所有可能的组合
  3. 去重策略：在同一层级的递归中，跳过相同的元素（除了第一个）
  4. 剪枝优化：当前和超过目标值时立即返回

去重的关键点：

  • 对于相同的元素，我们只在第一次遇到时考虑选择它
  • 在同一层的循环中，如果 candidates[i] == candidates[i-1] 且 i > start，则跳过
  • 这样可以避免产生重复的组合，如 [1,2] 和 [2,1] 被认为是同一个组合

时间复杂度分析： 最坏情况下需要枚举所有子集，时间复杂度为 O(2^n)，但实际运行中由于剪枝会快很多。

代码实现

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

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        path = []
        candidates.sort()
        
        def backtrack(start, target):
            if target == 0:
                result.append(path[:])
                return
            
            for i in range(start, len(candidates)):
                if candidates[i] > target:
                    break
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                
                path.append(candidates[i])
                backtrack(i + 1, target - candidates[i])
                path.pop()
        
        backtrack(0, target)
        return result

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

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

复杂度分析

复杂度类型复杂度说明
时间复杂度O(2^n)最坏情况下需要枚举所有子集，n为数组长度
空间复杂度O(target)递归栈深度最大为target（每次减少至少1），path数组空间也是O(target)

相关题目