全栈大前端

# 回溯

回溯算法是一种搜索法，试探法，它会在每一步做出选择，一旦发现这个选择无法得到期望结果，就回溯回去，重新做出选择。深度优先搜索利用的就是回溯算法思想。

本质类似 枚举

  • 适用场景

回溯算法很简单，它就是不断的尝试，直到拿到解。它的这种算法思想，使它通常用于解决广度的搜索问题，即从一组可能的解中，选择一个满足要求的解。

  • 解题思路
  1. 全局变量：保存结果
  2. 参数：递归函数的参数选择，通常是两种参数。 状态变量： result需要保存的值 条件变量： 判断搜索是否完毕以及搜索是否合法
  3. 完成条件： 完成条件是决定状态变量和条件变量取何值时可以判断整个搜索流程结束。整个搜索流程结束有两个含义：搜索成功并保存结果何搜索失败并返回上一次状态。
  4. 递归过程： 传递当前状态给下一次递归进行搜索。
  • 模版
let res = [];   //存储结果

function backtrack(path,condition,...){
    if(judge(condition)){  //满足条件
        res.push(path);
        return;
    }
    for(let select of selectList){
        if(剪枝条件) break;
        path.push(select);  // 走某条路
        backtrack(path,newSelectList);
        path.pop(); //返回上一个十字路口
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 高频题

  • 回溯

回溯

# 全排列

  • 回溯法

关键点：在递归之前做选择，在递归之后撤销选择。

  1. 借助 deepStack 栈暂存每一种枚举的可能情况
  2. 开启遍历枚举，已经选择过的数字不能再做选择。
  3. 在递归之前做选择，在递归之后需要撤销选择，恢复状态
  4. 完成所有遍历时，将deepStack 存入结果集res
const permute = function(nums) {
    const len = nums.length, res = [], deepStack = []
    const backtrack = (deepStack) => {
        // 递归终止条件
        if (deepStack.length == len) {
            return res.push(deepStack)
        }
        for (let i = 0; i < len; i++) {
            // 已经选择过的数字不能再做选择
            if (!deepStack.includes(nums[i])) {
                deepStack.push(nums[i]) // 做选择
                backtrack(deepStack.slice())
                deepStack.pop() // 撤销选择
            }
        }
    }
    backtrack(deepStack)
    return res
}

//时间复杂度: O(n * n!)
//空间复杂度: O(n * n!)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  • 递归
let permute =function (nums){
    //使用一个数组保存所有可能的全排列
    ler res =[]
    if(nums.length===0){
        return res
    }
    let used ={},path=[]
    dfs(nums,nums.length,0,path,used,res)
    return res
}
let dfs =function (nums,len,depth,path,used,res){
    //所有数都填完了
    if(depth ===len){
        res.push([...path])
        return 
    }
    for(let i= 0;i<len;i++){
        if(!used[i]){
            //动态维护数组
            path.push(nums[i])
            used[i]=true
            //继续递归下一个数
            dfs(nums,len,depth+1,path,used,res)
            //撤销操作
            used[i]=false 
            path.pop()
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

# 求子集

  • 回溯
  1. 对于数组中的每个元素都有两种选择：选或者不选。
  2. 对于当前迭代的元素，选择它就将其 push 后，基于选择后的状态从 start + 1 递归。
  3. 然后使用 pop 将其状态恢复，不选择当前迭代的元素从 start + 1 递归。
const subsets =function(nums)=>{
 const res =[]
 const dfs= function (start,cur){
     if(start===nums.length){
         res.push(cur.slice())
         return 
     }
     cur.push(nums[start])//选择
     dfs(start +1,cur)
     cur.pop()
     dfs(start +1,cur)
 }  
 dfs(0,[])
 return res
}


//时间复杂度: O(n * 2^n)，共 2^n 个状态，需要 O(n) 的时间来构造子集。
//空间复杂度: O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 电话号码的字母组合(中等) (opens new window)

  • 回溯 +借用map

  1. 使用回溯法进行求解，回溯是一种通过穷举所有可能情况来找到所有解的算法。

  2. 如果一个候选解最后被发现并不是可行解，回溯算法会舍弃它，并在前面的一些步骤做出一些修改，并重新尝试找到可行解。

  3. 如果没有更多的数字需要被输入，说明当前的组合已经产生。

  4. 如果还有数字需要被输入：

  5. 遍历下一个数字所对应的所有映射的字母。

  6. 将当前的字母添加到组合最后，也就是 str + tmp[r]

const letterCombinations = function (digits) {
    if (!digits) {
        return []
    }
    const len = digits.length
    const map = new Map()
    map.set('2', 'abc')
    map.set('3', 'def')
    map.set('4', 'ghi')
    map.set('5', 'jkl')
    map.set('6', 'mno')
    map.set('7', 'pqrs')
    map.set('8', 'tuv')
    map.set('9', 'wxyz')
    const result = []

    function generate(i, str) {
        if (i === len) {
            result.push(str)
            return
        }
        const tmp = map.get(digits[i])
        for (let r = 0; r < tmp.length; r++) {
            generate(i + 1, str + tmp[r])
        }
    }
    generate(0, '')
    return result
}
//时间复杂度：O(3^N * 4^M)
//空间复杂度：O(3^N * 4^M)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

# 组合(中等) (opens new window)

  • 回溯
  1. 每次递归当选满 k 个数时，将其推入最终集合。
  2. 回溯的过程中为了避免产生重复的组合，需要剪枝，通过指定下次递归的选择范围是 i + 1 来进行剪枝。
const combine =function (n,k){
    const res =[]
    const helper =function (start,cur){
        if(cur.length ===k){
            res.push(cur.slice())
            return 
        }
        for(let i =start; i<= n;i++){
            cur.push(i)
            helper(i+1,cur)
            cur.pop()
        }
    }
    helper(1,[])
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 组合总和(中等) (opens new window)

  1. 使用回溯法，不符合条件的情况进行剪枝。
  2. 当 cur === target 时，拷贝 arr 推进结果集。
  3. 从 start 开始遍历可选数组，选择当前数字后递归时注意要基于当前状态 i 继续选择，因为元素是可以重复进入集合的。
  4. 撤销选择，恢复状态。
const combinationSum = (candidates, target) => {
    const res = []
    // start: 起点索引 arr: 当前集合 cur: 当前所求之和
    const dfs = (start, arr, cur) => {
        if (cur > target) return
        if (cur === target) {
            res.push(arr.slice())
            return
        }
        for (let i = start; i < candidates.length; i++) {
            arr.push(candidates[i])
            dfs(i, arr, cur + candidates[i])
            arr.pop()
        }
    }
    dfs(0, [], 0)
    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# N皇后(困难) (opens new window)

  • 回溯
  1. 从上到下，从左到右遍历棋盘，准备好三个set分别记录列和两个对角线可以攻击到的坐标，
  2. 尝试在每个空位放置皇后，放置之后更新三个可以攻击到的set坐标，然后继续下一层遍历，完成下一层之后，尝试回溯当前层，也就是撤销当前层放置的皇后，
  3. 同时撤销三个可以攻击到的set坐标，不断回溯，直到遍历完成，找到所有可能的解。
const solveNQueens = (n) => {
    const board = new Array(n);
    for (let i = 0; i < n; i++) {
        board[i] = new Array(n).fill('.');//生成board
    }

    const cols = new Set();  // 列集，记录出现过皇后的列
    const diag1 = new Set(); // 正对角线集
    const diag2 = new Set(); // 反对角线集
    const res = [];//结果数组

    const backtrack = (row) => {
        if (row == n) {//终止条件
            const stringsBoard = board.slice();
            for (let i = 0; i < n; i++) {//生成字符串
                stringsBoard[i] = stringsBoard[i].join('');
            }
            res.push(stringsBoard);
            return;
        }
        for (let col = 0; col < n; col++) {
            // 如果当前点的所在的列，所在的对角线都没有皇后，即可选择，否则，跳过
            if (!cols.has(col) && !diag1.has(row + col) && !diag2.has(row - col)) {
                board[row][col] = 'Q';  // 放置皇后
                cols.add(col);          // 记录放了皇后的列
                diag2.add(row - col);   // 记录放了皇后的正对角线
                diag1.add(row + col);   // 记录放了皇后的负对角线
                backtrack(row + 1);
                board[row][col] = '.';  // 撤销该点的皇后
                cols.delete(col);       // 对应的记录也删一下
                diag2.delete(row - col);
                diag1.delete(row + col);
            }
        }
    };
    backtrack(0);
    return res;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

# N皇后II(困难) (opens new window)

  • 回溯

使用深度优先搜索配合位运算，二进制为 1 代表不可放置，0 相反 利用如下位运算公式：

  1. x & -x ：得到最低位的 1 代表除最后一位 1 保留，其他位全部为 0
  2. x & (x-1)：清零最低位的 1 代表将最后一位 1 变成 0
  3. x & ((1 << n) - 1)：将 x 最高位至第 n 位(含)清零
const totalNQueens =function(n){
    let res=0;
    const dfs =(n,row,cols,pie,na)=>{
        if(row >=n){
            res++;
            return; 
        }
        // 将所有能放置 Q的位置由 0变成1，以便 进行后续的位置遍历
        // 也就是得到当前所有空位
        let bits = (~(cols | pie | na)) & ((1 << n) - 1);
        while (bits) {
            // 取最低位的1
            let p = bits & -bits;
            // 把P位置上放入皇后
            bits = bits & (bits - 1);
            // row + 1 搜索下一行可能的位置
            // cols ｜ p 目前所有放置皇后的列
            // (pie | p) << 1 和 (na | p) >> 1) 与已放置过皇后的位置 位于一条斜线上的位置
            dfs(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1);
        }
    }
    dfs(n, 0, 0, 0, 0);
    return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

← 贪心 →