当前位置：首页 > article >正文

算法学习--回溯算法

article 2024/11/8 12:35:14

一、回溯算法思想：

本质是穷举，当发现不满足求解条件是，就回溯返回，尝试别的路径
重要的是找到嵌套逻辑和终止条件。

二、回溯算法模板：

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

回溯算法要素：
- 回溯（嵌套）逻辑和参数
- 回溯终止条件和存放结果方式
- 回溯搜索的循环体

三、leetcode

77. 组合 https://leetcode.cn/problems/combinations/
- 题目描述：返回范围 [1, n] 中所有可能的 k 个数的组合
- 题解思路：
  - 当求解1个数的所有组合时，我们可以使用1层for循环
  - 当求解2个数的所有组合时，我们可以使用2层for循环
  - 当求解k个数的所有组合时，我们可以使用k层for循环
  - for循环嵌套结束条件：当循环超过k层时，保存结果并返回。

39. 组合总数 https://leetcode.cn/problems/combination-sum/

题目描述：找给定数组can中元素满足数字和为target的不同组合（可重复）
解题思路：
- 首先确定回溯逻辑和参数：function backTrack(nums, sum, j)
  - nums是用来存储满足条件组合的数组，nums[i]代表的是这个组合包含can[i]的个数
  - sum是组合目前的数组和
  - j是代表目前正在搜索can的j位
- 接下来确定终止条件和存放结果方式
  - 终止条件1：当sum===target要输出结果，将nums数组转化为题目要求的组合形式然后添加到结果数组中
  - sum>targrt怎么办？通过在循环体中控制，只会sum<=target
  - 终止条件2：当j>=can.length时要return
- 确定回溯循环体逻辑
  - 搜索当前can[j]可能的个数i，i范围为i<=(target-sum)/can[j])
  - 需要注意的是，因为每个数组最后代表一种组合方式，所以要对数组进行处理，控制数组的第j位nums[i]代表的是这个组合包含can[i]的个数

最后JavaScript代码：

var combinationSum = function (can, target) {
    let ans = [];   //定义保存结果的数组
    function backTrack(nums, sum, j) {
        // console.log(nums,sum,j)
        if (sum === target) {        //保存结果的逻辑及终止条件1
            let arr = [];
            for (let i = 0; i < nums.length; i++) {
                for (let j = 0; j < nums[i]; j++) {
                    arr.push(can[i]);
                }
            }
            ans.push(arr);
            return;
        }
        if (j >= can.length) return;   //终止条件2
        for (let i = 0; i <= (target - sum) / can[j]; i++) {   //can[j]的个数为i时，循环体
            nums.push(i);
            backTrack(nums, sum + i * can[j], j + 1);
            nums.pop();         //保证下次循环时nums的长度符合要求
        }
    }
    backTrack([], 0, 0);   //调用函数
    return ans;   //返回最后结果
};

78. 子集 https://leetcode.cn/problems/subsets/description/

题目描述：返回数组的所有子集
解题思路1：77.组合的进阶版，在77中仅需输出k个数的组合，而此题需输出0-n个数的所有组合。77中元素是连续的，在这道题中，数组的下标也是连续的，可以借用下标去使用77中的逻辑。

JavaScript代码

var subsets = function(nums) {
    let ans=[];
    let n=nums.length;
    function backtrack(arr,m){   //arr为下标形式表示的子集
        if(arr.length===m){
            let array=arr.map(a=>nums[a]);
            ans.push(array);
            return;
        }
        for(let i=(arr[arr.length-1]+1)|0;i<=n-m+arr.length;i++){
            arr.push(i);
            backtrack(arr,m);
            arr.pop();
        }
    }
    for(let i=0;i<=n;i++){
        backtrack([],i);
    }
    return ans;
    
};

22. 括号生成 https://leetcode.cn/problems/generate-parentheses/description/

题目描述：生成n对括号所有的有效组合
解题思路1：在回溯的同时满足有效的规则，所谓有效的规则就是
- 左括号的个数>=右括号的个数
- 左括号的个数<=n

JavaScript代码

var generateParenthesis = function(n) {
    let ans=[];
    let arr=[];
    const backtrack=(a,b)=>{
        if(a==n&&b==n){
            ans.push(arr.join(''));
            return;
        }
        if(a>n||b>n)return
        if(a<n){
            arr.push('(');
            backtrack(a+1,b);
            arr.pop();
        }
        if(b<a){
            arr.push(')');
            backtrack(a,b+1);
            arr.pop();
        }
    }
    backtrack(0,0);
    return ans; 
};

51. N皇后 https://leetcode.cn/problems/n-queens/description/

题目描述：在n*n的棋盘上放n个皇后，要求不能在同一行、同一列、同一45度斜线，求解所有组合。
解题思路1：首先要理解清楚摆放规则，然后转化为代码
- 摆放规则就是当我们在讨论第n行的皇后位置时，不能与之前每一行的皇后处于同一列或者45度角的位置。如果存在这样的位置，那么继续递归。
- 终止/输出条件：当遍历完棋盘且有N个皇后时，保存结果，并且return

JavaScript代码：

var solveNQueens = function (n) {
    let ans = [];
    let arr = [];
    const backtrack = (a) => {   //代表第a行时的情况
        // console.log(a,arr)
        if (a === n) {
            let array = Array(n).fill(0).map(a=>Array(n).fill('.'));
            for (let i of arr) {
                array[i[0]][i[1]]='Q';
            }
            let tem=array.map(a=>a.join(''));
            ans.push(tem);
            return;
        }
        if (a > n) return
        for (let i = 0; i < n; i++) {
            if (arr.length == 0) {
                arr.push([0, i]);
                backtrack(a + 1);
                arr.pop();
            } else {
                let sig = 0;
                for (let j = 0; j < arr.length; j++) {
                    if (i === arr[j][1] || i === (arr[j][1] + a-arr[j][0] )|| i === (arr[j][1] - a+arr[j][0])) {
                        // console.log(arr)
                        sig = 1;
                    }
                }
                if (sig === 0) {
                    arr.push([a, i]);
                    backtrack(a + 1);
                    arr.pop();
                }
            }
        }
    }
    backtrack(0);
    return ans;
};

缺点：由于每次都要遍历棋盘的前几行，复杂度比较高。
52. N皇后2和此题基本一致，更简单了，输出只需要输出组合数量。

131. 分割回文串 https://leetcode.cn/problems/palindrome-partitioning/description/

题目描述：返回s所有的回文子串分割方案
解题思路：先利用动态规划将以第i个元素开头的回文串全部找到，然后再利用回溯进行组合输出

JavaScript代码：

var partition = function (s) {
    let n = s.length;
    const mark = Array(n).fill(0).map(a => Array(n).fill(false));  //动态规划标记矩阵
    const ans=[];
    const arr=Array(n).fill(0).map(a=>[]);   //将动态规划的结果保存在arr中
    const tem=[];   //临时矩阵，保存每次的结果
    /**动态规划来寻找所有的回文串 */
    for (let i = 0; i < n; i++) {
        mark[i][i] = true;
        arr[i].push(i);
    }
    for (let i = 0; i < n; i++) {
        if (i + 1 < n && s[i] === s[i + 1]) {
            mark[i][i+1]=true;
            arr[i].push(i+1);
            let a = 1;
            while (i - a >= 0 && i + a + 1 < n && mark[i - a + 1][i + a] === true) {
                if (s[i - a] === s[i + a + 1]) {
                    mark[i - a][i + a + 1] = true;
                    arr[i-a].push(i+a+1);
                }
                a++;
            }
        }
        let a = 1;
        while (i - a >= 0 && i + a < n && mark[i - a + 1][i + a - 1] === true) {
            if (s[i - a] === s[i + a]) {
                mark[i - a][i + a] = true;
                arr[i-a].push(i+a);
            }
            a++;
        }
    }
    // console.log(arr)
    /**将各个回文串按照不同的组合进行回溯输出 */
    const backtrack=(a)=>{
        if(a>=n){    //当需要递归的元素位数超过或等于n时，保存结果并回溯回去。
            ans.push(tem.slice());  
            return;
        }
        for(let i of arr[a]){
            tem.push(s.slice(a,i+1));   //将[a,i+1)范围的字符串加入tem
            backtrack(i+1);            //然后从i+1继续递归
            tem.pop();
        }
    }
    backtrack(0);
    return ans;
};