题目描述（题目难度，中等）
给定一个数组 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]
]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combination-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目求解
使用递归求解，递归的过程其实就是一个选数的过程，只要递归过程中，所选数的和不超过目标数 target，就把所选的数保存到临时列表中。一旦所选数的和等于 target，就将临时列表加入结果集。
参考代码如下：
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(candidates); // 去重的第一步
comSum(candidates, target, result, new ArrayList<>(), 0);
return result;
}
void comSum(int[] can, int tar, List<List<Integer>> res, List<Integer> canRes, int low){
if(tar == 0){
res.add(new ArrayList<>(canRes));
return;
}
for(int i = low; i < can.length; ++i){
if(i > low && can[i-1] == can[i]) continue; // 去重的第二步
if(can[i] <= tar){
canRes.add(can[i]);
comSum(can, tar-can[i], res, canRes, i+1);
canRes.remove(canRes.size()-1);
}else return;
}
}
}
递归函数最后一个参数表示的是选数的起始位置，i 表示当前所选数的位置，那么递归时最后一个实参置为 i+1，表示下次会在当前所选数的后面开始选数，这样就能满足题目“每个数字在每个组合中只能使用一次”的要求。
但由于 candidates 数组中本身会有重复数字出现，所以单纯按 和等于 target 的条件去选，会有重复的组合出现。为了在递归时就去掉重复组合，就需要将 candidates 数组排序，把相同的数聚在一起（其实只要能把相同的数聚在一起，不排序也可以），然后增加判断条件 i > low && can[i-1] == can[i]，就可以将重复组合过滤掉，这个条件一定要细心体会，leetcode 之前的题目三数之和的解法二中也使用了同样的方法去重。
网友评论