☆打卡算法☆LeetCode 40、组合总和 II 算法解析
☆打卡算法☆LeetCode 40、组合总和 II 算法解析
恬静的小魔龙
发布于 2022-08-07 10:00:14
发布于 2022-08-07 10:00:14
一、题目
1、算法题目
“给定一个数组和目标数，找出数组中所有可以使数组和为目标数的组合。”
40题跟39题的区别在于，40题不能包含重复的组合。
题目链接：
来源：力扣（LeetCode）
链接：40. 组合总和 II - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给定一个数组 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、思路分析
这个题需要求出所有和为目标数的组合，并且每个数只能使用一次，可以使用递归＋回溯的方法解决这个味问题。
首先，因为题目不能出现重复的组合，所以需要先将相同的数放在一起处理，也就是说，在递归的时候一起处理，这样就不会得到重复的组合。
使用哈希映射统计数组中每个数出现的次数，统计完放到一个列表中，在递归的时候调用。
2、代码实现
代码参考：
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;
}
}
image.png
3、时间复杂度
时间复杂度 ： O(n logn)
其中n是数组的长度。
空间复杂度： O(n)
需要O(n)的空间存储列表、递归张工存储当前选择的数的列表，以及递归需要的栈。
三、总结
这道题与39题的不同点就是去重，这也是这道题的难点。
39题可以使用回溯+递归的算法解题，但是并不适用本题，所以还需要改进回溯+递归算法，去除重复的组合。
去重可以使用哈希表，哈希表具有天然的去重功能，但是编码相对复杂，所以可以将不重复的按顺序搜索，在搜索的过程中检测分钟你是否会出现重复结果。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-11-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录