LeetCode 0040.组合总和 II：回溯 + 剪枝

【LetMeFly】40.组合总和 II：回溯 + 剪枝

力扣题目链接：https://leetcode.cn/problems/combination-sum-ii/

给定一个候选人编号的集合 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

解题方法：回溯（剪枝）

类似39.组合总和：回溯 + 剪枝，但这道题比较困难的地方在于，candidates中有重复的元素，而答案中不能有重复的数组。

怎么办呢，排序呗。刚开始还和之前一样走正常流程：

如果target已经达到则将当前方案加入答案数组。
如果已超target则直接返回
选当前元素并回溯
不选当前元素

不同之处在于，不选当前元素时，要保证选择的下一个元素和当前元素不同。

例如[4, 4, 5]，不选第一个4的话，就不能选第二个4。

否则的话，可能会出现第一个4和5、第二个4和5这两种相同的方案。

时间复杂度 $O(len(candidates)^2)$
空间复杂度 $O (l e n (c an d i d a t es))$

AC代码

C++

/** @Author: LetMeFly* @Date: 2025-01-26 07:27:24* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-26 07:57:37*/
class Solution {
private:vector<vector<int>> ans;vector<int> now;void dfs(vector<int>& c, int target, int index) {// 组合成功if (!target) {ans.push_back(now);return;}// 不再可能if (index == c.size() || target < 0) {return;}// 选当前now.push_back(c[index]);dfs(c, target - c[index], index + 1);now.pop_back();// 不选当前递归下一个int next = index;while (++next < c.size() && c[next] == c[index]);dfs(c, target, next);}
public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {sort(candidates.begin(), candidates.end());dfs(candidates, target, 0);return ans;}
};

Python

'''
Author: LetMeFly
Date: 2025-01-26 07:58:11
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-26 08:01:59
'''
from typing import Listclass Solution:def dfs(self, target: int, index: int) -> None:if not target:self.ans.append([i for i in self.now])returnif index == len(self.c) or target < 0:returnself.now.append(self.c[index])self.dfs(target - self.c[index], index + 1)self.now.pop()next = index + 1while next < len(self.c) and self.c[next] == self.c[index]:next += 1self.dfs(target, next)def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:candidates.sort()self.c = candidatesself.ans = []self.now = []self.dfs(target, 0)return self.ans

Java

/** @Author: LetMeFly* @Date: 2025-01-26 08:02:41* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-26 08:10:08*/
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;class Solution {private List<List<Integer>> ans;private List<Integer> now;private int[] c;private void dfs(int target, int index) {if (target == 0) {ans.add(new ArrayList<>(now));return;}if (index == c.length || target < 0) {return;}now.add(c[index]);dfs(target - c[index], index + 1);now.remove(now.size() - 1);int next = index;while (++next < c.length && c[next] == c[index]);dfs(target, next);}public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);c = candidates;ans = new ArrayList<>();now = new ArrayList<>();dfs(target, 0);return ans;}
}

Go

/** @Author: LetMeFly* @Date: 2025-01-26 08:47:10* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-26 09:01:49* @Descreption: AC,100.00%,34.12%*/
package mainimport "sort"func dfs(c []int, target int, now []int, index int, ans *[][]int) {if target == 0 {*ans = append(*ans, append([]int{}, now...))return}if index == len(c) || target < 0 {return}now = append(now, c[index])dfs(c, target - c[index], now, index + 1, ans)now = now[:len(now) - 1]next := index + 1for next < len(c) && c[next] == c[index] {next++}dfs(c, target, now, next, ans)
}func combinationSum2(candidates []int, target int) (ans [][]int) {var now []intsort.Ints(candidates)dfs(candidates, target, now, 0, &ans)return
}