【剑指 Offer II】 082. 含有重复元素集合的组合

题目：
给定一个可能有重复数字的整数数组 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

注意：本题与主站 40 题相同： https://leetcode-cn.com/problems/combination-sum-ii/

答案：

class Solution {
    List<List<Integer>> lists;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //回溯法,排序后去重
        Arrays.sort(candidates);
        lists = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        backTrace(list, candidates, target, 0);
        return lists;
    }
    public void backTrace(List<Integer> list, int[] candidates, int target, int index){
        if(target == 0){
            lists.add(new ArrayList<>(list));
            return;
        }
        if(index >= candidates.length) return;
        if(target < 0 && candidates[index] > 0) return;
        for(int i = index; i < candidates.length; i++){
            list.add(candidates[i]);
            backTrace(list, candidates, target - candidates[i], i + 1);
            while (i < candidates.length - 1 && candidates[i] == candidates[i + 1]) {
                i++;
            }
            list.remove(list.size() - 1);
        }
    }
}