剑指offer82：含有重复元素集合的组合

题目：
给定一个可能有重复数字的整数数组 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]
]
分析：
该题和之前几题的很大不同点在于输入的集合中有重复的数字但是输出不得包含重复的组合，如果输入的集合中有重复的数字，不经过特殊处理将产生重复的组合，例如，从集合[2,2,2]中选出2个数字本来能组成3个组合，但3个组合都是[2,2],因此它们是重复的组合，在该题中只能算1个。另外，组合不考虑数字的顺序，比如[2,2,4],[2,4,2],[4,2,2]只能算一个组合。、
该题思路的关键点：避免重复的组合的方法是当在某一步决定跳过某个值为m的数字时，跳过所有值为m的数字，例如，假设求[2,2,2]的组合，如果在处理第1个2时决定跳过它并跳过所有的2，那么得到的是一个空的组合，如果选择第1个2之后决定跳过第2个2并跳过后面的2，那么得到的是组合[2]。如果选择前两个2之后决定跳过第3个2，那么得到的是组合[2,2]。如果3个2都被选择，则得到组合[2,2,2]。采用这种方法则可避免两种产生重复组合[2,2]的情形。
为了方便跳过后面的所有值相同的数字，可以将集合中所有的数字排序，把相同的数字放在一起，这样更加方便比较数字，当决定跳过某个值的数字时，可以按顺序扫描后面的数字，直到找到不同的值为止。

代码：

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class CombinationSum2 {
    public static void main(String[] args) {
        CombinationSum2 combinationSum2 = new CombinationSum2();
        int[] nums = {2,2,2,4,3,3};
        List<List<Integer>> lists = combinationSum2.combinationSum2(nums, 8);
        System.out.println(lists);
    }
    public List<List<Integer>> combinationSum2(int[] nums, int target) {
//        排序是为了方便跳过相同的数字
        Arrays.sort(nums);
        List<List<Integer>> result = new LinkedList<>();
        LinkedList<Integer> combination = new LinkedList<>();
        helper(nums,target,0,combination,result);
        return result;
    }

    private void helper(int[] nums, int target, int i, LinkedList<Integer> combination, List<List<Integer>> result) {
        if (target == 0){
            result.add(new LinkedList<>(combination));
        }else if (target>0 && i<nums.length){
            helper(nums,target,getNext(nums,i),combination,result);
            combination.addLast(nums[i]);
            helper(nums,target-nums[i],i+1,combination,result);
            combination.removeLast();
        }
    }
//当决定跳过数字nums[i]时可以调用函数getNext找到与该数字不同的下一个数字。
    private int getNext(int[] nums, int index) {
        int next = index;
        while (next < nums.length && nums[next] == nums[index]){
            next++;
        }
        return next;
    }
}