22. 括号生成

这个的回溯技法 和 46 一样给了我很大的震撼。

  1. var generateParenthesis = function(n) {
  2.     let ans = [];
  4.     function dfs(leftP, rightP, strPath) {
  5.         if (strPath.length === 2 * n) {
  6.             ans.push(strPath);
  7.         }
  9.         if (leftP > 0) {
  10.             dfs(leftP - 1, rightP, `${strPath}(`)
  11.         }
  12.         if (leftP < rightP) {
  13.             dfs(leftP, rightP - 1, `${strPath})`)
  14.         }
  16.     }
  18.     dfs(n, n, '');
  20.     return ans;
  21. };

40. 组合总和 II

组合很简单，但是去重逻辑还是使用昨天和 491 以及 18

  1. var combinationSum2 = function(candidates, target) {
  2.     let n = candidates.length;
  3.     if (n === 0) {
  4.         return;
  5.     }
  7.     candidates.sort((a, b) => a - b);
  9.     let ans = [];
  11.     function dfs(path, start) {
  12.         let sum = path.reduce((pre, cur) => pre + cur, 0);
  14.         if (sum === target) {
  15.             ans.push(path);
  16.         }
  17.         if (sum >= target) {
  18.             return;
  19.         }
  21.         let used = new Set();
  22.         for (let i = start; i < n; i++) {
  23.             if (used.has(candidates[i])) {
  24.                 continue;
  25.             }
  27.             used.add(candidates[i]);
  28.             dfs([...path, candidates[i]], i + 1);
  29.         }
  30.     }
  32.     dfs([], 0);
  34.     return ans;
  35. };

216. 组合总和 III

  1. var combinationSum3 = function(k, n) { // 老方法
  2.     let ans = [];
  4.     function dfs(path, start) {
  5.         if (path.length === k) {
  6.             let sum = path.reduce((pre, cur) => pre + cur, 0);
  7.             if (sum === n) {
  8.                 ans.push(path);
  9.             }
  10.             return;
  11.         }
  13.         for (let i = start; i <= 9; i++) {
  14.             dfs([...path, i], i + 1);
  15.         }
  16.     }
  18.     dfs([], 1);
  20.     return ans;
  21. };

46. Permutations

在微软的面试中，一点都没写出来，奇耻大辱啊。

  1. var permute = function(nums) {
  2.     let n = nums.length;
  3.     if (n <= 1) {
  4.         return [[nums]]
  5.     }
  6.     let ans = [];
  7.     let used = new Array(n).fill(false); // 只借助一个多余数组就可以完成
  9.     function dfs(path) { // 本来是一个无数次的 for 循环，被轻松破解
  10.         if (path.length === n) { // 人为去找终止条件！！！
  11.             ans.push(path);
  12.             return;
  13.         }
  14.         for (let i = 0; i < n; i++) {
  15.             if (used[i]) {
  16.                 continue;
  17.             }
  18.             used[i] = true; // 仍然是前序操作
  19.             dfs([...path, nums[i]]);
  20.             used[i] = false; // 回溯
  21.         }
  22.     }
  24.     dfs([]);
  26.     return ans;
  27. };

47. Permutations II

加点料

  1. var permuteUnique = function(nums) {
  2.     let n = nums.length;
  3.     if (n <= 1) {
  4.         return [[nums]];
  5.     }
  6.     nums.sort((a, b) => a - b);
  7.     let ans = [];
  8.     let used = new Array(n).fill(false); // 通用状态记录
  10.     function dfs(path) {
  11.         if (path.length === n) { // 人为去找终止条件！！！
  12.             ans.push(path);
  13.             return;
  14.         }
  16.         let pre;
  17.         for (let i = 0; i < n; i++) {
  18.             if (used[i]) { // 状态1: 是否被祖先节点使用过
  19.                 continue;
  20.             }
  21.             if (nums[i] === pre) { // 状态2：是否与兄弟节点的值相同
  22.                 continue;
  23.             }
  25.             pre = nums[i];
  26.             if (!used[i]) {
  27.                 used[i] = true;
  28.                 dfs([...path, nums[i]]);
  29.                 used[i] = false;
  30.             }
  31.             // 不认真思考，很容易写成下面的样子
  32.             // if (nums[i] !== pre) {
  33.             //     pre = nums[i];
  34.             //     if (!used[i]) {
  35.             //         used[i] = true;
  36.             //         dfs([...path, nums[i]]);
  37.             //         used[i] = false;
  38.             //     }
  39.             // } else {
  40.             //     continue;
  41.             // }
  42.         }
  43.     }
  45.     dfs([]);
  47.     return ans;
  48. };

78. 子集

以下这个太复杂：（包含了使用set去重的步骤）

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[][]}
  4.  */
  5. /**
  6.  * @param {number[]} nums
  7.  * @return {number[][]}
  8.  */
  9. var subsets = function(nums) {
  10.     let n = nums.length;
  11.     if (n <= 0) {
  12.         return [];
  13.     }
  15.     let used = new Array(n).fill(false);
  16.     let ans_set = new Set(); // 使用set去重
  18.     function dfs(path) {
  19.         for (let i = 0; i < n; i++) {
  20.             if (used[i]) {
  21.                 continue;
  22.             }
  23.             used[i] = true;
  24.             let childPath = [...path, nums[i]].sort();
  25.             ans_set.add(childPath.join(','));
  26.             dfs(childPath);
  27.             used[i] = false;
  28.         }
  29.     }
  31.     dfs([]);
  33.     let result = Array.from(ans_set).map(item => item.split(','));
  34.     result.push([]);
  35.     return result;
  36. };

简单些：（把去重一并做了）

  1. var subsets = function(nums) {
  2.     let n = nums.length;
  3.     if (n <= 0) {
  4.         return [];
  5.     }
  6.     let ans = [];
  8.     function dfs(path, start) {
  9.         ans.push(path);
  11.         for (let i = start; i < n; i++) {
  12.             dfs([...path, nums[i]], i + 1); // 注意这里没有回溯的步骤
  13.         }
  14.     }
  16.     dfs([], 0);
  18.     return ans;
  19. };

把path写开，就有回溯了：

  1. var subsets = function(nums) {
  2.     let n = nums.length;
  3.     if (n <= 0) {
  4.         return [];
  5.     }
  6.     let ans = [];
  7.     let path = [];
  9.     function dfs(start) {
  10.         ans.push(path.slice(0));
  12.         for (let i = start; i < n; i++) {
  13.             path.push(nums[i]);
  14.             dfs(i + 1);
  15.             path.pop(); // 有了回溯
  16.         }
  17.     }
  20.     dfs(0);
  22.     return ans;
  23. };

90. 子集 II

和 47 排列问题一样的手段，要去重，先排序。

  1. var subsetsWithDup = function(nums) {
  2.     let n = nums.length;
  4.     nums.sort((a, b) => a - b); // 先排序去对付这种去重的问题
  6.     let ans_set = new Set();
  8.     function dfs(path, start) {
  9.         ans_set.add(path);
  11.         let pre;
  12.         for (let i = start; i < n; i++) {
  13.             if (pre !== nums[i]) {
  14.                 pre = nums[i];
  15.             } else {
  16.                 continue;
  17.             }
  19.             dfs([...path, nums[i]], i + 1);
  20.         }
  21.     }
  23.     dfs([], 0);
  25.     return Array.from(ans_set);
  26. };

491. 递增子序列

重点在于去重，看这样一个例子：
数组：x, y, 1(a), z,1(b), 1(c) ， 有3个相同的1，但是用括号 a b c 标明三个1 在 不同位置上。我们要从其中挑出两个元素，要求值不能重复：1(a), 1(b) 和 1(b) ,1(c) 是重复的
去重原理：
image.png
上图红色框到的两个部分就是相同的！
看代码实现：

  1. var findSubsequences = function(nums) {
  2.     let n = nums.length;
  3.     if (n <= 1) {
  4.         return [];
  5.     }
  7.     let ans = [];
  8.     // let used = [];
  10.     // function dfs(path, start) {
  11.     //     if (path.length > 1) {
  12.     //         ans.push(path);
  13.     //     }
  15.     //     let pre; // 只能检测相邻相等元素
  16.     //     for (let i = start; i < n; i++) {
  17.     //         if (pre === nums[i]) {
  18.     //             continue;
  19.     //         }
  21.     //         pre = nums[i];
  23.     //         used[nums[i]] = true;
  25.     //         let last = path.length ? path[path.length - 1] : -Infinity;
  26.     //         if (last <= nums[i]) {
  27.     //             dfs([...path, nums[i]], i + 1);
  28.     //         }
  29.     //     }
  30.     // }
  32.     function dfs(path, start) {
  33.         if (path.length >= 2) {
  34.             ans.push(path.slice(0));
  35.         }
  37.         let used = new Set(); // 能检测相邻或不相邻的 相等元素
  38.         for (let i = start; i < n; i++) {
  39.             if (used.has(nums[i])) {
  40.                 continue;
  41.             }
  43.             used.add(nums[i]);
  45.             let last = (path.length > 0) ? path[path.length - 1] : -Infinity;
  46.             if (last <= nums[i]) {
  47.                 dfs([...path, nums[i]], i + 1);
  48.             }
  49.         }
  50.     }
  52.     dfs([], 0);
  54.     return ans;
  55. };

18. 四数之和（和491相同的去重思路）

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number[][]}
  5.  */
  6. var fourSum = function(nums, target) {
  7.     nums.sort((a, b) => a - b);
  9.     let ans = [];
  11.     function dfs(path, start) {
  12.         if (path.length === 4) {
  13.             let sum = path.reduce((pre, cur) => pre + cur);
  14.             if (sum === target) {
  15.                 ans.push(path);
  16.             }
  17.             return sum;
  18.         }
  20.         let used = new Set();
  21.         for (let i = start; i < nums.length; i++) {
  22.             if (used.has(nums[i])) {
  23.                 continue;
  24.             }
  26.             used.add(nums[i]);
  28.             let sum = dfs([...path, nums[i]], i + 1);
  29.             if (sum !== undefined && sum >= target) { // add
  30.                 break;
  31.             } 
  32.         }
  34.     }
  36.     dfs([], 0);
  38.     return ans;
  39. };

除了四数之和，还能解决 三数之和。
小结：在求数组排列时，我们知道如何使用递归的方式去做，这里也是同样的要求选择三个数，道理一样。但是盲目递归是暴力解法，对于本题的条件
我们先对数组进行排列，将会大大减少时间复杂度。

51. N-Queens

动画解释（没玩过）：

  1. var solveNQueens = function(n) {
  2.     if (n <= 1) {
  3.         return [[nums]]
  4.     }
  5.     let ans = [];
  6.     let cols = new Set(); // used1
  7.     let dias1 = new Set(); // used2
  8.     let dias2 = new Set(); // used3
  10.     function dfs(row) {
  11.         if (row === n) { // 人为去找终止条件！！！
  12.             let tmp = [];
  13.             for (let col of cols) {
  14.                 let _tmp = new Array(n).fill('.');
  15.                 _tmp[col] = 'Q';
  16.                 tmp.push(_tmp);
  17.             }
  18.             ans.push(tmp);
  19.             return;
  20.         }
  22.         for (let i = 0; i < n; i++) {
  23.             if (cols.has(i)) {
  24.                 continue;
  25.             }
  26.             if (dias1.has(i - row)) {
  27.                 continue;
  28.             }
  29.             if (dias2.has(i + row)) {
  30.                 continue;
  31.             }
  33.             cols.add(i); // 仍然是前序操作
  34.             dias1.add(i - row);
  35.             dias2.add(i + row);
  36.             dfs(row + 1);
  37.             cols.delete(i)
  38.             dias1.delete(i - row);
  39.             dias2.delete(i + row);
  40.         }
  41.     }
  43.     dfs(0);
  45.     return ans;
  46. };

这里提出一个性概念，对于矩阵有斜列：
image.png
根据这样的新分法，矩阵里的内容可以重新被划分一次。非常巧妙。

37. 解数独

解题思路
亮点，不断从头重试
递归函数 用 两个 for 循环 嵌套 查询 列与行 的 格子，如果

  1. 不为空格

    不为空，有两种情况，1）棋盘初始值，2）棋盘的尝试值 （其实第二种情况在递归里被统一了）
    啥都不做，继续看下一个格子

  2. 为空格

每一个 空格试 1-9个数字，
1）如果9 个数字都不满足，则需要回溯；
2）如果有数字 i 满足，则将该空格，记录为 i, 再从头重试。这里填入的值，构成的 新的初始棋盘 再去求解。

何时是边界：

  1. 递归到 棋盘的最后一个空格，这时 试 1-9个数字，可以选出符合条件的数字，找到了本题的解。
  2. 如果 最后一个空格 也是 棋盘最后一行最后一列的位置，这时 棋盘全有值，构成的 新的初始棋盘 再去求解，全部通过，返回 true，无需回溯修改。
  1.  var solveSudoku = function(board) {
  2.     function isValid(row, col, val) {
  3.         let len = board.length
  4.         // 行不能重复
  5.         for(let i = 0; i < len; i++) {
  6.             if(board[row][i] == val) {
  7.                 return false
  8.             }
  9.         }
  10.         // 列不能重复
  11.         for(let i = 0; i < len; i++) {
  12.             if(board[i][col] == val) {
  13.                 return false
  14.             }
  15.         }
  16.         let startRow = Math.floor(row / 3) * 3
  17.         let startCol = Math.floor(col / 3) * 3
  19.         for(let i = startRow; i < startRow + 3; i++) {
  20.             for(let j = startCol; j < startCol + 3; j++) {
  21.                 if(board[i][j] == val) {
  22.                     return false
  23.                 }
  24.             }
  25.         }
  27.         return true
  28.     }
  30.     function backTracking() {
  31.         for(let i = 0; i < board.length; i++) {
  32.             for(let j = 0; j < board[0].length; j++) {
  33.                 if(board[i][j] !== '.') continue;
  34.                 for(let k = 1; k <= 9; k++) {
  35.                     if (isValid(i, j, k)) {
  36.                         board[i][j] = String(k); 
  37.                         if (backTracking()) return true; 
  38.                         board[i][j] = `.`
  39.                     }
  40.                 }
  41.                 return false
  42.             }
  43.         }
  45.         return true;
  46.     }
  48.     backTracking()
  49. };

39. Combination Sum

这道题我没有使用回溯，但是使用两处剪枝。

  1. var combinationSum = function(candidates, target) {
  2.     let ans = new Set();
  4.     function dfs(cans, tar, path) {
  5.         cans = cans.filter(can => can <= tar); // 剪枝 1
  6.         if (cans.length === 0) { // 人为去找终止条件！！！
  7.             let sum = path.reduce((pre, cur) => pre + cur, 0);
  9.             if (sum === target) {
  10.                 let tmp = path.sort((a, b) => a - b).join(',');
  11.                 ans.add(tmp);
  12.             }
  13.             return;
  14.         }
  16.         for (let num of cans) {
  17.             dfs(cans, tar - num, [...path, num]); // 剪枝 2
  18.         }
  19.     }
  21.     dfs(candidates, target, []);
  23.     return Array.from(ans).map(item => item.split(','))
  24. };

在去重的效率非常低：
image.png
之后看看别人是怎么写的，目前我对这类题的认知只有这么高了。

https://leetcode-cn.com/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

45. 跳跃游戏 II

这种技法可以解决很多问题，超乎想象

  1. var jump = function(nums) {
  2.     let ans = [];
  3.     function dfs(start, depth) {
  4.         if (start >= nums.length - 1) {
  5.             ans.push(depth);
  6.             return;
  7.         }
  9.         let steps = nums[start];
  10.         for (let i = 1; i <= steps; i++) {
  11.             dfs(start + i, depth + 1);
  12.         }
  13.     }
  15.     dfs(0, 0);
  17.     return Math.min(...ans);
  18. };