39. 组合总和

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

for 选择 in 选择列表:
    做选择
    backtrack(路径, 选择列表)
    撤销选择

class Solution {

    List<List<Integer>> res=new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //排序方便剪枝
        Arrays.sort(candidates);
        searchRes(candidates,0,target,new LinkedList<>());
        return res;
    }

    /**
     * path其实就是taget每次减的数字记录的值，如果我们target减为0的，那么该路径就是其和的路径了
     * 随着path变深，
     */
    public void searchRes(int[] candidates,int start, int target, LinkedList<Integer> path){
        //结束循环
        if (target<0){
            return;
        }
        if (target==0){
            res.add(new LinkedList<>(path));
            return;
        }

        //每次从自己和自己后面的数字遍历即可减少很多重复计算
        for (int i = start; i < candidates.length; i++) {
            // 如果target<当前数，则跳过
            // 因为如果target小于当前值也就说当前值已不能构成path的加数了，不然总值会大于taget
            if (target<candidates[i]) {
                break;
            };
            path.add(candidates[i]);
            searchRes(candidates,i,target-candidates[i],path);
            //回撤
            path.removeLast();
        }


    }
}