LeetCode刷题系列 -- 40. 组合总和 II

给定一个候选人编号的集合 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 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/combination-sum-ii
 

思路：回溯算法秒杀所有排列/组合/子集问题 :: labuladong的算法小抄

回溯算法。
1. 数组排序
2. 定义数组  used ，长度为  nums.length , used[i] 代表 nums[i] 是否被放入子集中
3. 回溯算法遍历数组。注意剪枝问题：

java：

class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new LinkedList<>();
        boolean[] used = new boolean[candidates.length];
 
        Arrays.sort(candidates);
 
        backtrack(candidates, target, 0, 0,used, new LinkedList<>(), result);
 
        return result;
    }
 
    public void backtrack(int[] candidates, int target, int start, int subSetSum, boolean[] used,List<Integer> subSet, List<List<Integer>> result) {
        if(subSetSum==target) {
            result.add(new LinkedList<>(subSet));
            return;
        }
 
        // 组合的和大于 target 时，就不需要再递归了
        if(subSetSum>target) {
            return;
        }
 
        for(int i=start;i<candidates.length;i++) {
 
            // 剪枝。 与前面的子集 II 的剪枝逻辑是一样的，相同的元素不需要再递归一次，不然就重复了
            if(i>0&&candidates[i-1] == candidates[i] && !used[i-1]) {
                continue;
            }
            
            used[i] = true;
            subSetSum += candidates[i];
            subSet.add(candidates[i]);
            backtrack(candidates,target,i+1,subSetSum,used,subSet,result);
            used[i] = false;
            subSetSum -= candidates[i];
            subSet.remove(subSet.size()-1);
        }
 
    }
}