【剑指 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);        }    }}