回溯法寻找组合

常见的使用DFS+回溯求解组合问题

    private ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {


        if (num == null){
            return new ArrayList<>();
        }

        Arrays.sort(num);
        findCombination(num,0,target,new ArrayList<>());

        Collections.sort(list, new Comparator<ArrayList<Integer>>() {
            @Override
            public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {

                Iterator<Integer> iterator1 = o1.iterator();
                Iterator<Integer> iterator2 = o2.iterator();

                while (iterator1.hasNext() && iterator2.hasNext()){

                    Integer next1 = iterator1.next();
                    Integer next2 = iterator2.next();

                    if (next1 < next2){
                        return -1;
                    }else if (next1 > next2){
                        return 1;
                    }
                }

                return 0;
            }
        });

        return list;
    }

    private void findCombination(int[] num,int index, int target, List<Integer> curlist){

        if (target == 0){

            ArrayList<Integer> newlist = new ArrayList<>(curlist);
            Collections.sort(newlist);
            list.add(newlist);
            return;
        }

        if (index >= num.length || target < 0){
            return;
        }

        for (int i = index; i < num.length; i++) {

            if (i > index && num[i] == num[i-1]){
                continue;
            }

            curlist.add(num[i]);
            findCombination(num,i+1,target-num[i],curlist);
            curlist.remove(curlist.size()-1);
        }
    }