“给定一个数组和目标数,找出数组中所有可以使数组和为目标数的组合。”
40题跟39题的区别在于,40题不能包含重复的组合。
题目链接:
来源:力扣(LeetCode)
链接:40. 组合总和 II - 力扣(LeetCode) (leetcode-cn.com)
给定一个数组 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]
]
这个题需要求出所有和为目标数的组合,并且每个数只能使用一次,可以使用递归+回溯的方法解决这个味问题。
首先,因为题目不能出现重复的组合,所以需要先将相同的数放在一起处理,也就是说,在递归的时候一起处理,这样就不会得到重复的组合。
使用哈希映射统计数组中每个数出现的次数,统计完放到一个列表中,在递归的时候调用。
代码参考:
public class Solution {
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
Array.Sort(candidates);
IList<IList<int>> lstAllRes = new List<IList<int>>();
Stack<int> path = new Stack<int>();
dfs(candidates, target, candidates.Length, 0, path, lstAllRes);
return lstAllRes;
}
private void dfs(int[] nums, int target, int n, int begin, Stack<int> path, IList<IList<int>> lstAllRes){
if(SumOfStack(path) == target){
lstAllRes.Add(new List<int>(path));
return;
}else if(SumOfStack(path) > target){
return;
}
for(int i = begin; i < n; i++){
if(i > begin && nums[i] == nums[i - 1]){
continue;
}
path.Push(nums[i]);
dfs(nums, target, n, i + 1, path, lstAllRes);
path.Pop();
}
}
private int SumOfStack(Stack<int> stack){
int res = 0;
foreach(int num in stack){
res += num;
}
return res;
}
}
时间复杂度 : O(n logn)
其中n是数组的长度。
空间复杂度: O(n)
需要O(n)的空间存储列表、递归张工存储当前选择的数的列表,以及递归需要的栈。
这道题与39题的不同点就是去重,这也是这道题的难点。
39题可以使用回溯+递归的算法解题,但是并不适用本题,所以还需要改进回溯+递归算法,去除重复的组合。
去重可以使用哈希表,哈希表具有天然的去重功能,但是编码相对复杂,所以可以将不重复的按顺序搜索,在搜索的过程中检测分钟你是否会出现重复结果。