40. 组合总和 II（难度：中等）
题目描述：
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
- 所有数字（包括目标数）都是正整数。
- 解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
[1,2,2],
[5]
]
解法一：回溯法 + 剪枝
分析：
首先我们先分析题目，要求找出candidates数组中所有可以相加组合为target的全部组合，而且所有组合不能重复，和上到题唯一的区别就是每个数字只能使用一次，而且在candidates数组中会出现重复的元素。
那么既然给的数组中有重复的元素，但是需要的结果中又不能有重复组合，那么我们可以先对candidates数组进行排序，然后遍历回溯，那么我们拿到的满足条件的组合一定都是有序的，再借助set集合的不重复的特点，来保存结果组合集，可以保证结果组合的唯一性。
回溯：
和上到题一样的思路，我们可以利用回溯的思想，每次遍历拿到一个数字t，让 target - t，然后继续递归，找到可以组合为 target - t 的数字组合。
- 当 target = 0时，就说明找到了符合条件的列表，将列表加入结果集中。
- 当 target < candidates[i]时，说明了从第i个元素开始，后面的都将不满足条件，那么就可以直接break，进行剪枝。
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
Set<List<Integer>> result = new HashSet();
recall(result,new ArrayList<>(),candidates,target,-1);
List<List<Integer>> list = new ArrayList<>(result);
return list;
}
private void recall(Set<List<Integer>> result, ArrayList arrayList, int[] candidates, int target,int start) {
if(target == 0) {
result.add(new ArrayList<>(arrayList));
}
for(int i = start+1;i<candidates.length;i++) {
if(target < candidates[i]) break;
arrayList.add(candidates[i]);
recall(result, arrayList, candidates, target - candidates[i], i);
arrayList.remove(arrayList.size()-1);
}
}
}
