[算法]BFS | DFS | 回溯

Mediumacktracking
能解决贪心、动态规划的大部分问题。
适用场景： 小规模数据问题
缺点：相当于穷举， 复杂度高， 指数级别。

• 题型一：排列、组合、子集相关问题
• 题型二：Flood Fill（洪水）
• 题型三：字符串中的回溯问题
• 题型四：游戏问题

练习1：

面试题 08.07. 无重复字符串的排列组合

case 1: “qwe” => [“qwe”, “qew”, “wqe”, “weq”, “ewq”, “eqw”]
case 2: “ab” => [“ab”, “ba”]

/**
 * @param {string} S
 * @return {string[]}
 */
var permutation = function(S) {
    let res = [];
    let arr = [...S];
    let prev = [];
    let record = new Array(S.length).fill(false);
    dfs(arr, 0, prev, record, res);
    return res;
};
function dfs(arr, depth, prev, record, res) {
    if (depth == arr.length) {
        res.push(prev.join(''));
        return;
    }
    for (let i = 0; i < arr.length; i++) {
        if (record[i]) {
            continue;
        }
        prev.push(arr[i]);
        record[i] = true;
        dfs(arr, depth + 1, prev, record, res);
        prev.pop();
        record[i] = false;
    }
}

剪枝：剑指 Offer 38. 字符串的排列(面试题 08.08. 有重复字符串的排列组合)

“abc” => [“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]
📢 出现重复字符 “aab” => [“aba”,”aab”,”baa”]
解决关键：

1. 排序
2. 判断相邻进行剪枝i > 0 && arr[i] == arr[i-1] && record[i-1] ``` var permutation = function(S) { let res = []; let arr = […S]; arr.sort(); // 关键 let prev = []; let record = new Array(S.length).fill(false); dfs(arr, 0, prev, record, res); return res; };

function dfs(arr, depth, prev, record, res) { if (depth == arr.length) { res.push(prev.join(‘’)); return; } for (let i =0; i < arr.length; i++) { if (record[i]) { continue } // 剪枝，重复字符 if (i > 0 && arr[i] == arr[i-1] && record[i-1]) { continue } prev.push(arr[i]); record[i] = true dfs(arr, depth+1, prev, record, res); // 回溯 prev.pop() record[i] = false } }

<a name="csZiN"></a>
#### 美团：var arr =[[‘A’,’B’],[‘a’,’b’],[1,2]] 求二维数组的全排列组合  结果：Aa1,Aa2,Ab1,Ab2,Ba1,Ba2,Bb1,Bb2

function compose(…args) { // console.log(args) var res = [] dfs(args, 0, [], res) console.log(res.length, res) return res }

function dfs(arr, depth, prev, res) { if (depth == arr.length) { res.push(prev.join(‘’)); return } for (let i of arr[depth]) { prev.push(i) dfs(arr, depth+1, prev, res) prev.pop() } }

compose(‘abc’, ‘ABC’) compose(‘ab’, ‘AB’, ‘12’)

// 9 (9) [“aA”, “aB”, “aC”, “bA”, “bB”, “bC”, “cA”, “cB”, “cC”] // 1test:5 8 (8) [“aA1”, “aA2”, “aB1”, “aB2”, “bA1”, “bA2”, “bB1”, “bB2”]

<a name="JCOC7"></a>
#### 给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合
n = 4,k = 2  => [ [ 1, 2 ], [ 1, 3 ], [ 1, 4 ], [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]

function combine (n, k) { let res = []; let prev = []; dfs(n, k, 0, prev, res); return res; }

function dfs(n, k, start, prev, res) { if (prev.length == k) { res.push(prev.slice()); return; } for (let i=start; i<n; i++) { prev.push(i+1); dfs(n, k, i+1, prev, res); prev.pop(); } }

// case 1 console.log(combine(4, 2))

<a name="qJb5y"></a>
## 练习2：
<a name="yadK6"></a>
#### [面试题 08.09. 括号](https://leetcode-cn.com/problems/bracket-lcci/)
case 1: 3 =><br />[<br />  "((()))",<br />  "(()())",<br />  "(())()",<br />  "()(())",<br />  "()()()"<br />]

depth<br />0              null<br />                 /\<br />1             (       ~~)~~<br />           /   \        <br />2       ((       ()    <br />        |         |    \<br />3      (()       ()(    ~~())~~<br />    |         |<br />4      (())       ()()

var generateParenthesis = function(n) { let res = []; dfs(n, 0, 0, ‘’, res); return res; };

function dfs (n, left, right, prev, res) { if (left == n && right == n) { res.push(prev); return; } if (left < n) { dfs(n, left+1, right, prev+’(‘, res) } if (right < left) { dfs(n, left, right+1, prev+’)’, res) } }

<a name="cNyeP"></a>
#### [面试题 08.04. 幂集](https://leetcode-cn.com/problems/power-set-lcci/)
case 1: nums = [1,2,3]<br />[<br />  [3],<br />  [1],<br />  [2],<br />  [1,2,3],<br />  [1,3],<br />  [2,3],<br />  [1,2],<br />  []<br />]

var subsets = function(nums) { let prev = []; let res = []; dfs(nums, 0, prev, res); return res; };

function dfs (nums, depth, prev, res) { res.push(prev.slice()); for (let i = depth; i< nums.length; i++) { prev.push(nums[i]); // dfs(nums, depth+1, prev, res); 错误写法 depth++; // 注意 dfs(nums, depth, prev, res); // 回溯 prev.pop(); } }

<a name="YdLhI"></a>
#### [5759. 找出所有子集的异或总和再求和](https://leetcode-cn.com/problems/sum-of-all-subset-xor-totals/)

var subsetXORSum = function(nums) { let n = nums.length; let res = []; let prev = 0; dfs(nums, 0, prev, res); return res.reduce((a, c) => a + c, 0) };

function dfs(nums, depth, prev, res) { res.push(prev); for (let i = depth; i < nums.length; i++) { prev ^= nums[i]; depth++; dfs(nums, depth, prev, res); // bracktrack prev ^= nums[i]; } }

<a name="CECZD"></a>
## 练习3：
<a name="D5i3z"></a>
#### [784. 字母大小写全排列](https://leetcode-cn.com/problems/letter-case-permutation/)

var letterCasePermutation = function(S) { let prev = []; let res = []; dfs(S, 0, prev, res); return res; };

function dfs(S, depth, prev, res) { if (depth == S.length) { res.push(prev.slice().join(‘’)); return; } let cur = S.charAt(depth); if ((/[a-zA-Z]/).test(cur)) { cur = cur.toLocaleLowerCase(); } prev.push(cur); dfs(S, depth+1, prev, res); prev.pop(); if ((/[a-z]/).test(cur)) { prev.push(cur.toLocaleUpperCase()); dfs(S, depth+1, prev, res); prev.pop(); } } ```

93. 复原IP地址