一、题目
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; } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度 ： O(n logn)
其中n是数组的长度。
空间复杂度： O(n)
需要O(n)的空间存储列表、递归张工存储当前选择的数的列表，以及递归需要的栈。
三、总结
这道题与39题的不同点就是去重，这也是这道题的难点。
39题可以使用回溯+递归的算法解题，但是并不适用本题，所以还需要改进回溯+递归算法，去除重复的组合。
去重可以使用哈希表，哈希表具有天然的去重功能，但是编码相对复杂，所以可以将不重复的按顺序搜索，在搜索的过程中检测分钟你是否会出现重复结果。
