Leetcode【39】Combination Sum（Java版）

这是一道典型的回溯法

具体回溯法的入门参考我的一篇博客

https://blog.csdn.net/ssjdoudou/article/details/103988511

这里我们关心的是数组，因为可以重复添加，所以每次遍历都是从第一个开始，不管当前的临时列表有几个值，我们都把候选列表从第一个开始往后试，如果不对，就剪枝（退回上一步），然后再用backtrack去试

package com.company;

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

public class combinationSum {

    public static void main(String[] args){
        combinationSum test = new combinationSum();
        int[] t = {2,3,6,7};
        System.out.print(test.combinationSum(t,7));
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target){
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> tmp = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates,target,0,res,tmp);
        return res;
    }

    public void backtrack(int[] candidates,int target,int start,List<List<Integer>> res,List<Integer> tmp){
        if(target < 0) return;
        else if(target == 0){
            res.add(new ArrayList<>(tmp));
            return;
        }else{
            for(int i = start; i < candidates.length; i++){
                if (i < 0) break;
                tmp.add(candidates[i]);
                backtrack(candidates, target - candidates[i], i, res, tmp);
                tmp.remove(tmp.size() - 1);
            }
        }
    }
}