【hot100-java】【组合总和】

R8-回溯篇

印象题，很基本的回溯

class Solution {
    void backtrack(List<Integer> state,int target,int[] choices,int start,List<List<Integer>> ret){
        //子集和等于target，记录解
        if (target==0){
            ret.add(new ArrayList<>(state));
            return;
        }
        //遍历所有选择
        //剪枝2：从start开始遍历，避免生成重复子集
        for (int i=start;i<choices.length;i++){
            //剪枝1：若子集和超过target，直接结束循环
            if (target-choices[i]<0){
                break;
            }
            //做出选择,更新target
            state.add(choices[i]);
            //进行下一轮选择
            backtrack(state,target-choices[i],choices,i,ret);
            //回退:撤销选择，恢复到之前的状态
            state.remove(state.size()-1);
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //状态子集
        List<Integer>state=new ArrayList<>();
        Arrays.sort(candidates);
        int start=0;
        //结果子集
        List<List<Integer>> ret=new ArrayList<>();
        backtrack(state,target,candidates,start,ret);
        return ret;
    }
}

PS：

java语法 

1.移除数组最后一个元素

state.remove(state.size()-1);

2.使用数组接受传入的参数值

new ArrayList<>(state)

3.ret数组后面增加值

ret.add()

4.数组排序，例如candidates是一个数组

Arrays.sort(candidates);