package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class demo_40 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        //记录每一次List中数的和
        int sum=0;
        Arrays.sort(candidates);
        backtrack(list, new ArrayList<Integer>(), candidates, target,0,sum);
        System.out.println(list);
        return list;
    }
    
    public void backtrack(List<List<Integer>> list,List<Integer> alist,int[] candidates,int target,int j,int sum) {
        //数组最大的和都无法小于target，则无解
        if(sum<target&&alist.size()==candidates.length) {return ;}
        if(sum==target) {
            list.add(new ArrayList<Integer>(alist));
        }
        else {
            for(int i=j;i<candidates.length;i++) {
                //去除重复
                if(i>j&&candidates[i]==candidates[i-1]){continue;}
                j=i;
                alist.add(candidates[i]);
                sum=sum+candidates[i];
                if(sum<=target) {
                    backtrack(list, alist, candidates, target, j+1,sum);
                }
                else {
                    sum=sum-candidates[i];
                    alist.remove(alist.size()-1);
                    break;
                }
                sum=sum-candidates[i];
                alist.remove(alist.size()-1);
            }
        }
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        demo_40 d40 =new demo_40();
        int[] candidates= {10,1,2,7,6,1,5};
        d40.combinationSum2(candidates,8);
    }
}