【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);

原文地址：https://blog.csdn.net/m0_73629042/article/details/142413121

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！