📐算法 回溯

📐算法回溯

发表于 2021/04/19 更新于 2023/10/07

作者 zhangz1w3nCode

3 分钟阅读

1.方法总结💡

回溯方法本质是递归 通过对一个数组或字符串 进行逐个组合 得出结果

2.适用题型🎯

  类似于"排列组合"/"二维穷举"的题型

3.注意点❗

1️⃣.回溯本质是递归-尤其注意递归结束的条件
2️⃣.注意审题 看题目是否能组合/选择重复的值 或者是已经选择过的值
3️⃣.注意 回溯体内的条件 1.开始条件start  2.执行的次数
4️⃣.执行回溯的时候根据题意 选择对参数进行增加或者减少

4.模板🔑

  
class Solution {

    List<List<Integer>> res = new ArrayList(); //记录所有的结果
    List<Integer> path = new ArrayList();	   //记录每次回溯的结果

    public List<List<Integer>> Method(int[] nums, int k) {
        backTrace(nums,k,0);//开始进入回溯    backTrace 想象成是行row    里面的for循环是 列 col
        return res;		   //返回结果
    }


    public void backTrace(int nums,int k ,int start){

        if(k==0){//⚠回溯停止的条件
            res.add(new ArrayList(path)); //把每次回溯的结果添加到res集合
            return;//return结束方法
        }


        for(int i=start;i<=n-k+1;++i){    //⚠每次进行的回溯  1.i是开始位置  2,回溯长度  3.自增
            path.add(i);				//结果添加到 path集合
            backTrace(n,k+1,i+1);         //再进回溯(k增加或者减少是根据题目来 i加或者减根据能否取到自身)
            path.remove(path.size()-1);  //把之前添加的 元素 删除
        }


    }

}