剪枝
排除那些不符合条件的分支。进步程序的运行效率。
回溯：
一层层递归，尝试搜素答案，
- 找到答案：返回后果，尝试其余的分支
- 找不到答案：返回上一层，尝试其余分支
回溯模版：
result = [];
function backtrack (path, list) {if (满足条件) {result.push(path);
return
}
for () {
// 单层逻辑
backtrack (path, list)
// 撤销抉择 重置状态
}
}回溯四部曲：
- 回溯参数
- 终止条件
- 单层递归逻辑
- 抉择其余分支（撤销抉择 重置状态）
473. 火柴拼正方形 (medium)
你将失去一个整数数组 matchsticks，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你能够把它们连在一起，而且每根火柴棒必须 应用一次。
如果你能使这个正方形，则返回 true，否则返回 false。
示例 1:
输出: matchsticks = [1,1,2,2,2]
输入: true
解释: 能拼成一个边长为 2 的正方形，每边两根火柴。
示例 2:输出: matchsticks = [3,3,3,3,4]
输入: false
解释: 不能用所有火柴拼成一个正方形。提醒:
1 <= matchsticks.length <= 15
1 <= matchsticks[i] <= 108
- 思路：排序 nums 数组，缩小回溯的次数。一直尝试将 nums 中的元素放入 4 个桶中，如果都能放的下，则能拼成正方形
js：
// 例子：[1,2,2,2,1]
var makesquare = function (nums) {function backtrack(i, nums, edge, bucket) {if (i >= nums.length) {// 递归完结条件
return true;
}
for (let j = 0; j < 4; j++) {// 循环 4 个桶
if (bucket[j] + nums[i] > edge) {// 这个桶装不下 持续找下一个桶
continue;
}
bucket[j] += nums[i];// 将以后元素退出桶中
if (backtrack(i + 1, nums, edge, bucket)) {// 索引 i 加 1 持续递归下一个 nums 中的元素
return true;// 下一个元素能放进桶中
}
bucket[j] -= nums[i];// 回溯状态
}
return false;// 循环完结都没放进适合的桶 那不能形成正方形
}
if (nums.length < 4) {//nums 长度小于 4 间接不能形成正方形
return false;
}
let sum = 0;
for (let i = 0; i < nums.length; i++) {sum += nums[i];
}
if (sum % 4) {//nums 的和不能整除 4 不能形成正方行
return false;
}
nums.sort((a, b) => b - a);// 排序 nums
let bucket = Array(4).fill(0);// 筹备 4 个桶
return backtrack(0, nums, sum / 4, bucket);// 传入 nums 元素的索引 i，nums，一个边长，和桶 bucket
};52. N 皇后 II(hard）
n 皇后问题 钻研的是如何将 n 个皇后搁置在 n × n 的棋盘上，并且使皇后彼此之间不能互相攻打。
给你一个整数 n，返回 n 皇后问题 不同的解决方案的数量。
示例 1：
输出：n = 4
输入：2
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：输出：n = 1
输入：1提醒：
1 <= n <= 9
办法 1. 位运算
js:
var totalNQueens = function (n) {if (n < 1) return
let count = 0;
dfs(n, 0, 0, 0, 0)
return count
//n: 皇后的数量
//row：以后行
//cols：搁置皇后的地位
//diag1：能够攻打的左歪斜对角线
//diag2：能够攻打的右歪斜对角线
function dfs(n, row, cols, diag1, diag2) {if (row >= n) {// 递归终止 统计解法
count += 1;
return
}
//~(cols | diag1 | diag2)：攻打的地位合起来 取反之后，1 的地位就是能够搁置皇后的地位
//(1 << n) - 1：从右向左，大于 n 的地位都变成 0
//(~(cols | diag1 | diag2)) & ((1 << n) - 1)：从右向左，能够搁置皇后的地位，大于 n 的地位都变成 0
let bits = (~(cols | diag1 | diag2)) & ((1 << n) - 1)
while (bits) {
let p = bits & -bits// 取到从右向左第一个 1
bits = bits & (bits - 1)// 去掉从右向左第一个 1
// 列和两个对角线合上不能够搁置的二进制位
dfs(n, row + 1, cols | p, (diag1 | p) << 1, (diag2 | p) >>> 1)
}
}
};79. 单词搜寻（medium）
给定一个 m x n 二维字符网格 board 和一个字符串单词 word。如果 word 存在于网格中，返回 true；否则，返回 false。
单词必须依照字母程序，通过相邻的单元格内的字母形成，其中“相邻”单元格是那些程度相邻或垂直相邻的单元格。同一个单元格内的字母不容许被重复使用。
示例 1：
输出：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
输入：true
示例 2：输出：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “SEE”
输入：true
示例 3：输出：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCB”
输入：false提醒：
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成进阶：你能够应用搜寻剪枝的技术来优化解决方案，使其在 board 更大的状况下能够更快解决问题？
-
思路：从上到下，左到右遍历网格，每个坐标递归调用
check(i, j, k)函数，i,j 示意网格坐标，k 示意 word 的第 k 个字符，如果能搜寻到第 k 个字符返回 true，否则返回 false，check 函数的终止条件有 2 种状况- 如果 i，j 地位的字符和字符串地位 k 的字符不相等，则这条搜寻门路搜寻失败 返回 false
- 如果搜寻到了字符串的结尾，则找到了网格中的一条门路，这条门路上的字符正好能够组成字符串 s
两种状况都不满足则把以后网格节点退出
visited数组，visited示意节点曾经拜访过了，而后顺着以后网格坐标的四个方向持续尝试，如果没找到 k 开始的子串，则回溯状态visited[i] [j] = false，持续前面的尝试。 - 复杂度剖析：工夫复杂度
O(MN⋅3^L)，M,N 为网格的长度与宽度，L 为字符串 word 的长度，第一次调用check函数的时候，进行 4 个方向的查看，其余坐标的节点都是 3 个方向查看，走过去的分支不会反方向回去，所以check函数的工夫复杂度是3^L，而网格有M*N个坐标，且存在剪枝，所以最坏的状况下工夫复杂度是O(MN⋅3^L)。空间复杂度是O(MN)，visited数组空间是O(MN)，check递归栈的最大深度在最坏的状况下是O(MN)
办法 1: 回溯
Js:
var exist = function(board, word) {const h = board.length, w = board[0].length;// 网格的长和宽
const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];// 方向数组
const visited = new Array(h);// 标记是否拜访过的数组
for (let i = 0; i < visited.length; ++i) {// 初始化 visited 数组
visited[i] = new Array(w).fill(false);
}
const check = (i, j, s, k) => {// 查看从网格 i，j 登程是否能搜寻到 0 - k 的字符组成的子串
// 如果 i，j 地位的字符和第 k 个的字符不相等，则这条搜寻门路搜寻失败 返回 false
if (board[i][j] != s.charAt(k)) {
return false;
// 如果搜寻到了字符串的结尾，则找到了网格中的一条门路，这条门路上的字符正好能够组成字符串 s
} else if (k == s.length - 1) {return true;}
visited[i][j] = true;// 标记 i，j 被拜访过了
let result = false;
for (const [dx, dy] of directions) {// 向 i，j 的四个方向持续尝试寻找
let newi = i + dx, newj = j + dy;
if (newi >= 0 && newi < h && newj >= 0 && newj < w) {// 新的坐标地位非法查看
if (!visited[newi][newj]) {// 新的坐标不能存在于 visited 中，也就是不能是拜访过的
const flag = check(newi, newj, s, k + 1);// 持续查看新的坐标
if (flag) {// 如果在网格中找到了字符串 则跳过循环
result = true;
break;
}
}
}
}
visited[i][j] = false;// 回溯状态
return result;// 返回后果
}
for (let i = 0; i < h; i++) {for (let j = 0; j < w; j++) {const flag = check(i, j, word, 0);
if (flag) {return true;}
}
}
return false;
};17. 电话号码的字母组合 (medium)
给定一个仅蕴含数字 2-9 的字符串，返回所有它能示意的字母组合。答案能够按 任意程序 返回。
给出数字到字母的映射如下（与电话按键雷同）。留神 1 不对应任何字母。
示例 1：
输出：digits = “23”
输入：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]
示例 2：输出：digits = “”
输入：[]
示例 3：输出：digits = “2”
输入：[“a”,”b”,”c”]提醒：
0 <= digits.length <= 4
digits[i] 是范畴 [‘2’, ‘9’] 的一个数字。
办法 1.dfs+ 回溯
- 思路：深度优先遍历，遍历函数传入每一层造成的字符串和一个指向字符的地位指针，打给你指针的地位达到字符串的结尾时，将造成的字符串退出后果数组，递归的每一层遍历这一层的数字对应的字符，而后传入新的字符，指针向后挪动一次，一直递归
- 复杂度：工夫复杂度
O(3^m * 4^n)，m，n 别离是三个字母和四个字母对应的数字个数。空间复杂度O(m+n)，递归栈的深度，最大为m+n
js：
// 输出：digits = "23"
// 输入：["ad","ae","af","bd","be","bf","cd","ce","cf"]
var letterCombinations = (digits) => {if (digits.length == 0) return [];
const res = [];
const map = {// 建设电话号码和字母的映射关系
2: "abc",
3: "def",
4: "ghi",
5: "jkl",
6: "mno",
7: "pqrs",
8: "tuv",
9: "wxyz",
};
const dfs = (curStr, i) => {//curStr 是递归每一层的字符串，i 是扫描的指针
if (i > digits.length - 1) {// 边界条件，递归的进口
res.push(curStr); // 其中一个分支的解推入 res
return; // 完结递归分支，进入另一个分支
}
const letters = map[digits[i]]; // 取出数字对应的字母
for (const l of letters) {
// 进入不同字母的分支
dfs(curStr + l, i + 1); // 参数传入新的字符串，i 右移，持续递归
}
};
dfs("", 0); // 递归入口，传入空字符串，i 初始为 0 的地位
return res;
};办法 2.bfs
- 思路：用队列广度优先遍历，先循环数字数组，而后取出对应的字母，与以后层的字符串组成新的字符串退出队列，遍历实现之后，队列的最初一层就是解。
- 复杂度：工夫复杂度
O(3^m * 4^n)，m，n 别离是三个字符和四个字母对应的数组个数。空间复杂度O(3^m * 4^n)，队列的空间大小，最大为3^m * 4^n
js：
var letterCombinations = (digits) => {if (digits.length == 0) return [];
const map = {
2: "abc",
3: "def",
4: "ghi",
5: "jkl",
6: "mno",
7: "pqrs",
8: "tuv",
9: "wxyz",
};
const queue = [];
queue.push("");
for (let i = 0; i < digits.length; i++) {// 循环数字的每个字符
const levelSize = queue.length; // 以后层的节点个数
for (let j = 0; j < levelSize; j++) {const curStr = queue.shift(); // 以后层的字符串
const letters = map[digits[i]];// 获取数字对应的字母字符
for (const l of letters) {queue.push(curStr + l); // 新生成的字符串入列
}
}
}
return queue; // 最初一层生成的字符串就是解
};51. N 皇后（hard）
依照国际象棋的规定，皇后能够攻打与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 钻研的是如何将 n 个皇后搁置在 n×n 的棋盘上，并且使皇后彼此之间不能互相攻打。
给你一个整数 n，返回所有不同的 n 皇后问题 的解决方案。
每一种解法蕴含一个不同的 n 皇后问题 的棋子搁置计划，该计划中 ‘Q’ 和 ‘.’ 别离代表了皇后和空位。
示例 1：
输出：n = 4
输入：[[“.Q..”,”…Q”,”Q…”,”..Q.”],[“..Q.”,”Q…”,”…Q”,”.Q..”]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：输出：n = 1
输入：[[“Q”]]提醒：
1 <= n <= 9
起源：力扣（LeetCode）
链接：https://leetcode.cn/problems/…
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。
办法 1. 回溯
动画过大，点击查看
- 思路：从上到下，从左到右遍历棋盘，筹备好三个 set 别离记录列和两个对角线能够攻打到的坐标，尝试在每个空位搁置皇后，搁置之后更新三个能够攻打到的 set 坐标，而后持续下一层遍历，实现下一层之后，尝试回溯以后层，也就是撤销以后层搁置的皇后，同时撤销三个能够攻打到的 set 坐标，一直回溯，直到遍历实现，找到所有可能的解。
- 复杂度剖析：工夫复杂度：
O(N!)，其中 N 是皇后数量，因为每个皇后必须位于不同列，因而曾经搁置的皇后所在的列不能搁置别的皇后。第一个皇后有 N 列能够抉择，第二个皇后最多有 N- 1 列能够抉择 …。空间复杂度：O(N)，其中 N 是皇后数量，空间复杂度次要取决于递归调用层数、记录每行搁置的皇后列下标的数组以及三个汇合，递归调用层数不会超过 N，数组的长度为 N，每个汇合的元素个数都不会超过 N。
js:
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;
};36. 无效的数独 (medium)
请你判断一个 9 x 9 的数独是否无效。只须要 依据以下规定，验证曾经填入的数字是否无效即可。
数字 1-9 在每一行只能呈现一次。
数字 1-9 在每一列只能呈现一次。
数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能呈现一次。（请参考示例图）留神：
一个无效的数独（局部已被填充）不肯定是可解的。
只须要依据以上规定，验证曾经填入的数字是否无效即可。
空白格用 ‘.’ 示意。示例 1：
输出：board =
[[“5″,”3″,”.”,”.”,”7″,”.”,”.”,”.”,”.”]
,[“6″,”.”,”.”,”1″,”9″,”5″,”.”,”.”,”.”]
,[“.”,”9″,”8″,”.”,”.”,”.”,”.”,”6″,”.”]
,[“8″,”.”,”.”,”.”,”6″,”.”,”.”,”.”,”3″]
,[“4″,”.”,”.”,”8″,”.”,”3″,”.”,”.”,”1″]
,[“7″,”.”,”.”,”.”,”2″,”.”,”.”,”.”,”6″]
,[“.”,”6″,”.”,”.”,”.”,”.”,”2″,”8″,”.”]
,[“.”,”.”,”.”,”4″,”1″,”9″,”.”,”.”,”5″]
,[“.”,”.”,”.”,”.”,”8″,”.”,”.”,”7″,”9″]]
输入：true
示例 2：输出：board =
[[“8″,”3″,”.”,”.”,”7″,”.”,”.”,”.”,”.”]
,[“6″,”.”,”.”,”1″,”9″,”5″,”.”,”.”,”.”]
,[“.”,”9″,”8″,”.”,”.”,”.”,”.”,”6″,”.”]
,[“8″,”.”,”.”,”.”,”6″,”.”,”.”,”.”,”3″]
,[“4″,”.”,”.”,”8″,”.”,”3″,”.”,”.”,”1″]
,[“7″,”.”,”.”,”.”,”2″,”.”,”.”,”.”,”6″]
,[“.”,”6″,”.”,”.”,”.”,”.”,”2″,”8″,”.”]
,[“.”,”.”,”.”,”4″,”1″,”9″,”.”,”.”,”5″]
,[“.”,”.”,”.”,”.”,”8″,”.”,”.”,”7″,”9″]]
输入：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其余数字均与 示例 1 雷同。但因为位于左上角的 3×3 宫内有两个 8 存在, 因而这个数独是有效的。提醒：
board.length == 9
board[i].length == 9
boardi 是一位数字（1-9）或者 ‘.’
办法 1：回溯
- 思路：筹备行、列、3 3 小方块，三个哈希表或者 set 或者 9 9 的二维数组，都能够，只有能判反复即可，从上到下，从左到右循环，顺次查看行、列、3 * 3 小方块中是否有反复的数字，如果有则返回 false，而后更新哈希表或者 set。
- 复杂度剖析：工夫复杂度：
O(1)，数独共有 81 个单元格，每个单元格遍历一次即可。空间复杂度：O(1)，数独的大小固定，因而哈希表的空间也是固定的。
Js:
var isValidSudoku = function(board) {
// 方向判重
let rows = {};// 行
let columns = {};// 列
let boxes = {};//3* 3 小方块
// 遍历数独
for(let i = 0;i < 9;i++){for(let j = 0;j < 9;j++){let num = board[i][j];
if(num != '.'){// 遇到无效的数字
let boxIndex = parseInt((i/3)) * 3 + parseInt(j/3);// 子数独序号
if(rows[i+'-'+num] || columns[j+'-'+num] || boxes[boxIndex+'-'+num]){// 反复检测
return false;
}
// 方向 + 数字 组成惟一键值，若呈现第二次，即为反复
// 更新三个对象
rows[i+'-'+num] = true;
columns[j+'-'+num] = true;
boxes[boxIndex+'-'+num] = true;
}
}
}
return true;
};46. 全排列（medium）
给定一个不含反复数字的数组 nums，返回其 所有可能的全排列。你能够 按任意程序 返回答案。
示例 1：
输出：nums = [1,2,3]
输入：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：输出：nums = [0,1]
输入：[[0,1],[1,0]]
示例 3：输出：nums = [1]
输入：[[1]]提醒：
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不雷同
- 思路：筹备 path 数组，寄存每一个回溯递归的分支中的数字排列，调用回溯函数 传入 nums，nums 长度，used 数组，used 示意曾经应用的数字，回溯函数中循环 nums 中的数，每层循环将 nums 中的元素退出 path 中，而后递归调用回溯函数，调用实现之后，回溯之前的状态，当 path 数组的长度和 nums 的长度雷同就找到了一种排列。
- 复杂度：工夫复杂度
O(n*n!)。空间复杂度O(n)，递归栈深度
js：
var permute = function(nums) {const res = [], path = [];
backtracking(nums, nums.length, []);// 调用回溯函数 传入 nums，nums 长度，used 数组
return res;
function backtracking(n, k, used) {if(path.length === k) {// 递归终止条件
res.push(Array.from(path));
return;
}
for (let i = 0; i < k; i++) {if(used[i]) continue;// 曾经应用过了就跳过本轮循环
path.push(n[i]);
used[i] = true;
backtracking(n, k, used);// 递归
path.pop();// 回溯 将 push 进的元素 pop 进去 而后标记成未应用 持续其余分支
used[i] = false;
}
}
};22. 括号生成（medium）
数字 n 代表生成括号的对数，请你设计一个函数，用于可能生成所有可能的并且 无效的 括号组合。
示例 1：
输出：n = 3
输入：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2：输出：n = 1
输入：[“()”]提醒：
1 <= n <= 8
办法 1: 暴力
复杂度剖析：工夫复杂度O(2^2n*n)，字符串的长度为2n，每个地位有两种抉择，抉择左或者右括号，验证字符串是否无效复杂度O(n)，剪枝之后会优化，最坏的状况是O(2^2n*n)。空间复杂度O(n), 递归次数最多 2n
办法 2. 递归 dfs
- 思路：采纳递归，终止条件是字符串的长度等于
2n，递归函数传入构建的字符串，左右括号残余多少，每个地位有两种抉择，抉择左或者右括号，这里能够进行剪枝优化，只有右括号的保有数量大于左括号的保有数量，能力选右括号，否则必定不能形成无效括号
Js:
const generateParenthesis = (n) => {const res = []; // 输入的后果数组
const generate = (str, left, right) => {if (str.length == 2 * n) { // 字符串构建实现
res.push(str); // 将字符串退出 res
return; // 完结以后递归（完结以后搜寻分支）}
if (left > 0) { // 只有左括号有剩，能够选它，持续递归做抉择
generate(str + '(', left - 1, right);
}
if (right > left) { // 右括号的保有数量大于左括号的保有数量，能力选右括号
generate(str + ')', left, right - 1);
}
};
generate('', n, n); // 递归的入口，初始字符串是空字符串，初始括号数量都是 n
return res;
};办法 3. 回溯
- 思路：当左括号剩下的多，阐明字符串中的左括号数量少于右括号，不非法，对字符串尝试增加左括号，而后回溯，尝试增加右括号，而后尝试回溯
Js:
var generateParenthesis = function(n) {if (n == 0) return []
const res = []
let track = []
backtrack(n, n, track, res)
return res
function backtrack(left, right, track, res) {
// 数量小于 0，不非法
if (left < 0 || right < 0) return
// 若左括号剩下的多，阐明不非法
if (right < left) return
// 所有括号用完，失去非法组合
if (left == 0 && right == 0) {res.push(track.join(''))
return
}
// 尝试增加左括号
track.push('(')
// 这个中央肯定要留神 须要拷贝一份 track，也就是采纳[...track]，不然会影响其余分支
backtrack(left - 1, right, [...track], res)
track.pop()
// 尝试增加右括号
track.push(')')
backtrack(left, right - 1, [...track], res)
track.pop()}
};37. 解数独(hard)
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规定：
数字 1-9 在每一行只能呈现一次。
数字 1-9 在每一列只能呈现一次。
数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能呈现一次。（请参考示例图）
数独局部空格内已填入了数字，空白格用 ‘.’ 示意。示例 1：
输出：board = [[“5″,”3″,”.”,”.”,”7″,”.”,”.”,”.”,”.”],[“6″,”.”,”.”,”1″,”9″,”5″,”.”,”.”,”.”],[“.”,”9″,”8″,”.”,”.”,”.”,”.”,”6″,”.”],[“8″,”.”,”.”,”.”,”6″,”.”,”.”,”.”,”3″],[“4″,”.”,”.”,”8″,”.”,”3″,”.”,”.”,”1″],[“7″,”.”,”.”,”.”,”2″,”.”,”.”,”.”,”6″],[“.”,”6″,”.”,”.”,”.”,”.”,”2″,”8″,”.”],[“.”,”.”,”.”,”4″,”1″,”9″,”.”,”.”,”5″],[“.”,”.”,”.”,”.”,”8″,”.”,”.”,”7″,”9″]]
输入：[[“5″,”3″,”4″,”6″,”7″,”8″,”9″,”1″,”2”],[“6″,”7″,”2″,”1″,”9″,”5″,”3″,”4″,”8”],[“1″,”9″,”8″,”3″,”4″,”2″,”5″,”6″,”7”],[“8″,”5″,”9″,”7″,”6″,”1″,”4″,”2″,”3”],[“4″,”2″,”6″,”8″,”5″,”3″,”7″,”9″,”1”],[“7″,”1″,”3″,”9″,”2″,”4″,”8″,”5″,”6”],[“9″,”6″,”1″,”5″,”3″,”7″,”2″,”8″,”4”],[“2″,”8″,”7″,”4″,”1″,”9″,”6″,”3″,”5”],[“3″,”4″,”5″,”2″,”8″,”6″,”1″,”7″,”9”]]
解释：输出的数独如上图所示，惟一无效的解决方案如下所示：提醒：
board.length == 9
board[i].length == 9
boardi 是一位数字或者 ‘.’
题目数据 保障 输出数独仅有一个解
- 思路：循环行和列，尝试在每个地位搁置 1 -9，并测验合法性，包含行、列、3 * 3 方块的合法性，如果非法持续循环，直到找到一个非法的解，如果不非法，则回溯状态，并持续尝试其余的可能性
- 复杂度剖析：同 36 题
js:
var solveSudoku = function(board) {function isValid(row, col, val, board) {
let len = board.length
// 行中的数字不能反复
for(let i = 0; i < len; i++) {if(board[row][i] === val) {return false}
}
// 列中的数字不能反复
for(let i = 0; i < len; i++) {if(board[i][col] === val) {return false}
}
let startRow = Math.floor(row / 3) * 3
let startCol = Math.floor(col / 3) * 3
// 方块中的数字不能反复
for(let i = startRow; i < startRow + 3; i++) {for(let j = startCol; j < startCol + 3; j++) {if(board[i][j] === val) {return false}
}
}
return true
}
function backTracking() {// 回溯函数
for(let i = 0; i < board.length; i++) {for(let j = 0; j < board[0].length; j++) {// 循环行和列
if(board[i][j] !== '.') continue
for(let val = 1; val <= 9; val++) {// 尝试在以后单元格搁置 1 -9
if(isValid(i, j, `${val}`, board)) {// 判断搁置数字的合法性
board[i][j] = `${val}`// 搁置数字
if (backTracking()) {// 非法返回 ture
return true
}
board[i][j] = `.`// 不非法回溯状态
}
}
return false//1- 9 的数字都不非法，返回 false
}
}
return true// 全副可能性都尝试实现 返回 true 阐明有解
}
backTracking()
return board
};77. 组合 (medium)
给定两个整数 n 和 k，返回范畴 [1, n] 中所有可能的 k 个数的组合。
你能够按 任何程序 返回答案。
示例 1：
输出：n = 4, k = 2
输入：
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2：输出：n = 1, k = 1
输入：[[1]]提醒：
1 <= n <= 20
1 <= k <= n
- 思路：回溯函数传入 n，k 和抉择的元素地位 startIndex，在每层递归中，从 startIndex 开始循环到
n - (k - path.length) + 1的地位，将这些数退出 path，而后 startIndex 加 1，持续递归函数进入下一个分支，实现调用之后回溯状态，当 path 的长度等于 k 的时候终止这层分支，退出后果中。 - 复杂度：工夫复杂度：
O(C(n, k) * k)，枚举后果总数为C(n, k)，每次失去一个后果须要O(k)工夫。空间复杂度：O(n)，最大是 n 层递归栈。
js：
const combine = (n, k) => {const res = [];
const helper = (startIndex, path) => { //startIndex 示意搜寻的终点地位 path 是每条分支的一个组合）if (path.length == k) {res.push(path.slice()); // 须要拷贝一份 防止受其余分支的影响
return;
}
for (let i = startIndex; i <= n - (k - path.length) + 1; i++) {// 剪枝
path.push(i); // 退出 path
helper(i + 1, path); // 下一层递归
path.pop(); // 回溯状态}
};
helper(1, []); // 递归入口
return res;
}视频解说：传送门