package leetcode;

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

public class demo_39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        Arrays.sort(candidates);
        backtrack(list, new ArrayList<Integer>(), candidates, target,0);
        System.out.println(list);
        return list;
    }
    
    public void backtrack(List<List<Integer>>list,List<Integer> li,int[] nums,int target,int j) {
        if(sumList(li)==target) {
            list.add(new ArrayList<Integer>(li));
        }else {
            for(int i=j;i<nums.length;i++){
                //当前数组的起始位置不能超过上一次循环的起始位置
                j=i;
                li.add(nums[i]);
                if(sumList(li)<=target) {
                    backtrack(list, li, nums, target,j);
                }
                else {
                    li.remove(li.size()-1);
                    break;
                }
                li.remove(li.size()-1);
            }
        }
    }
    
    //判断当前List中的和是否满足target
    public int sumList(List<Integer> li) {
        int sum=0;
        for(int i:li) {
            sum=sum+i;
        }
        return sum;
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        demo_39 d39=new demo_39();
        int candidates[]= {2,3,6,7};
        d39.combinationSum(candidates, 7);
    }

}