大厂算法面试之leetcode精讲11剪枝&回溯
视频解说（高效学习）:点击学习
目录：
1.开篇介绍
2.工夫空间复杂度
3.动静布局
4.贪婪
5.二分查找
6.深度优先&广度优先
7.双指针
8.滑动窗口
9.位运算
10.递归&分治
11剪枝&回溯
12.堆
13.枯燥栈
14.排序算法
15.链表
16.set&map
17.栈
18.队列
19.数组
20.字符串
21.树
22.字典树
23.并查集
24.其余类型题
剪枝
排除那些不符合条件的分支。进步程序的运行效率。
回溯：
一层层递归，尝试搜素答案，
- 找到答案：返回后果，尝试其余的分支
- 找不到答案：返回上一层，尝试其余分支
回溯模版：
result = [];function backtrack (path, list) { if (满足条件) { result.push(path); return } for () { // 单层逻辑 backtrack (path, list) // 撤销抉择 重置状态 }}回溯四部曲：
- 回溯参数
- 终止条件
- 单层递归逻辑
- 抉择其余分支（撤销抉择 重置状态）
22. 括号生成 （medium）
办法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;};Java:
class Solution { List<String> res = new ArrayList<>(); public List<String> generateParenthesis(int n) { generate(n, n, ""); return res; } private void generate(int left, int right, String curStr) { if (left == 0 && right == 0) { res.add(curStr); return; } if (left > 0) { generate(left - 1, right, curStr + "("); } if (right > left) { generate(left, right - 1, curStr + ")"); } }}办法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() }};Java:
class Solution { public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<String>(); backtrack(res, new StringBuilder(), 0, 0, n); return res; } public void backtrack(List<String> res, StringBuilder cur, int left, int right, int max) { if (cur.length() == max * 2) { res.add(cur.toString()); return; } if (left < max) { cur.append('('); backtrack(res, cur, left + 1, right, max); cur.deleteCharAt(cur.length() - 1); } if (right < left) { cur.append(')'); backtrack(res, cur, left, right + 1, max); cur.deleteCharAt(cur.length() - 1); } }}51. N 皇后 （hard）
办法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;};java:
class Solution { public List<List<String>> solveNQueens(int n) { List<List<String>> res = new ArrayList<List<String>>(); int[] queens = new int[n]; Arrays.fill(queens, -1); Set<Integer> cols = new HashSet<Integer>(); Set<Integer> diag1 = new HashSet<Integer>(); Set<Integer> diag2 = new HashSet<Integer>(); backtrack(res, queens, n, 0, cols, diag1, diag2); return res; } public void backtrack(List<List<String>> res, int[] queens, int n, int row, Set<Integer> cols, Set<Integer> diag1, Set<Integer> diag2) { if (row == n) { List<String> board = generateBoard(queens, n); res.add(board); } else { for (int i = 0; i < n; i++) { if (cols.contains(i)) { continue; } int diagonal1 = row - i; if (diag1.contains(diagonal1)) { continue; } int diagonal2 = row + i; if (diag2.contains(diagonal2)) { continue; } queens[row] = i; cols.add(i); diag1.add(diagonal1); diag2.add(diagonal2); backtrack(res, queens, n, row + 1, cols, diag1, diag2); queens[row] = -1; cols.remove(i); diag1.remove(diagonal1); diag2.remove(diagonal2); } } } public List<String> generateBoard(int[] queens, int n) { List<String> board = new ArrayList<String>(); for (int i = 0; i < n; i++) { char[] row = new char[n]; Arrays.fill(row, '.'); row[queens[i]] = 'Q'; board.add(new String(row)); } return board; }}52. N皇后 II(hard）
办法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) } }};Java:
class Solution { public int totalNQueens(int n) { return dfs(n, 0, 0, 0, 0); } public int dfs(int n, int row, int clos, int diag1, int diag2) { if (row == n) { return 1; } else { int count = 0; int bits = ((1 << n) - 1) & (~(clos | diag1 | diag2)); while (bits != 0) { int position = bits & (-bits); bits = bits & (bits - 1); count += dfs(n, row + 1, clos | position, (diag1 | position) << 1, (diag2 | position) >> 1); } return count; } }}36. 无效的数独 (medium)
办法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;};Java:
class Solution { public boolean isValidSudoku(char[][] board) { int[][] rows = new int[9][9];//用数组同样实现 int[][] columns = new int[9][9]; int[][][] boxes = new int[3][3][9]; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { char c = board[i][j]; if (c != '.') { int index = c - '0' - 1; rows[i][index]++; columns[j][index]++; boxes[i / 3][j / 3][index]++; if (rows[i][index] > 1 || columns[j][index] > 1 || boxes[i / 3][j / 3][index] > 1) { return false; } } } } return true; }}37. 解数独(hard)
- 思路：循环行和列，尝试在每个地位搁置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 };Java:
class Solution { public void solveSudoku(char[][] board) { backTracking(board); } private boolean backTracking(char[][] board){ for (int i = 0; i < 9; i++){ // 遍历行 for (int j = 0; j < 9; j++){ // 遍历列 if (board[i][j] != '.'){ continue; } for (char k = '1'; k <= '9'; k++){ //尝试在以后地位搁置1-9 if (isValid(i, j, k, board)){ board[i][j] = k;//搁置数字 if (backTracking(board)){ //非法返回ture return true; } board[i][j] = '.'; } } return false;//1-9的数字都不非法，返回false } } return true;//全副可能性都尝试实现 返回true 阐明有解 } private boolean isValid(int row, int col, char val, char[][] board){ // 同行是否反复 for (int i = 0; i < 9; i++){ if (board[row][i] == val){ return false; } } // 同列是否反复 for (int j = 0; j < 9; j++){ if (board[j][col] == val){ return false; } } // 小方块中的元素是否反复 int startRow = (row / 3) * 3; int startCol = (col / 3) * 3; for (int i = startRow; i < startRow + 3; i++){ for (int j = startCol; j < startCol + 3; j++){ if (board[i][j] == val){ return false; } } } return true; }}79. 单词搜寻（medium）
思路：从上到下，左到右遍历网格，每个坐标递归调用
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;};Java:
class Solution { public boolean exist(char[][] board, String word) { int h = board.length, w = board[0].length; boolean[][] visited = new boolean[h][w]; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { boolean flag = check(board, visited, i, j, word, 0); if (flag) { return true; } } } return false; } public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) { if (board[i][j] != s.charAt(k)) { return false; } else if (k == s.length() - 1) { return true; } visited[i][j] = true; int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; boolean result = false; for (int[] dir : directions) { int newi = i + dir[0], newj = j + dir[1]; if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) { if (!visited[newi][newj]) { boolean flag = check(board, visited, newi, newj, s, k + 1); if (flag) { result = true; break; } } } } visited[i][j] = false; return result; }}46. 全排列 （medium）
- 思路：筹备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; } }};java：
class Solution { List<List<Integer>> result = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); boolean[] used; public List<List<Integer>> permute(int[] nums) { if (nums.length == 0){ return result; } used = new boolean[nums.length]; permuteHelper(nums); return result; } private void permuteHelper(int[] nums){ if (path.size() == nums.length){ result.add(new ArrayList<>(path)); return; } for (int i = 0; i < nums.length; i++){ if (used[i]){ continue; } used[i] = true; path.add(nums[i]); permuteHelper(nums); path.removeLast(); used[i] = false; } }}77. 组合 (medium)
- 思路：回溯函数传入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;}java：
class Solution { List<List<Integer>> result = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> combine(int n, int k) { combineHelper(n, k, 1); return result; } private void combineHelper(int n, int k, int startIndex){ if (path.size() == k){ result.add(new ArrayList<>(path)); return; } for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){ path.add(i); combineHelper(n, k, i + 1); path.removeLast(); } }}17. 电话号码的字母组合 (medium)
办法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;};java：
class Solution { String[] map = { " ", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; public List<String> letterCombinations(String digits) { if (digits == null || digits.length() == 0) { return new ArrayList<>(); } dfs(digits, new StringBuilder(), 0); return res; } List<String> res = new ArrayList<>(); void dfs(String digits, StringBuilder curStr, int index) { if (index == digits.length()) { res.add(curStr.toString()); return; } char c = digits.charAt(index); int pos = c - '0'; String map_string = map[pos]; for (int i = 0; i < map_string.length(); i++) { curStr.append(map_string.charAt(i)); dfs(digits, curStr, index + 1); curStr.deleteCharAt(curStr.length() - 1); } }}办法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; //最初一层生成的字符串就是解};java：
class Solution { public List<String> letterCombinations(String digits) { if (digits == null || digits.length() == 0) { return new ArrayList<String>(); } String[] map = { " ", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" }; List<String> res = new ArrayList<>(); res.add(""); for (int i = 0; i < digits.length(); i++) { String letters = map[digits.charAt(i) - '0']; int levelSize = res.size(); for (int j = 0; j < levelSize; j++) { String tmp = res.remove(0); for (int k = 0; k < letters.length(); k++) { res.add(tmp + letters.charAt(k)); } } } return res; }}78. 子集 (medium)
- 思路：回溯函数传入字符开始的地位startIndex，一直递归，每一层startIndex加1，当一个分支完结之后在，开始回溯，进入另一个分支。
- 复杂度：工夫复杂度
O(n*2^n)，如图递归进去的状态是2^n个状态，每个状态构建path数组复杂度是O(n)。空间复杂度O(n)，也就是递归栈的空间
js：
//例子：nums = [1,2,3]var subsets = function(nums) { let result = []//寄存后果 let path = []//寄存一个分支的后果 function backtracking(startIndex) {//startIndex字符递归开始的地位 result.push(path.slice())//path.slice()断开和path的援用关系 for(let i = startIndex; i < nums.length; i++) {//从startIndex开始递归 path.push(nums[i])//以后字符推入path backtracking(i + 1)//startIndex向后挪动一个地位 持续递归 path.pop()//回溯状态 } } backtracking(0) return result};java：
class Solution { List<List<Integer>> result = new ArrayList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> subsets(int[] nums) { if (nums.length == 0){ result.add(new ArrayList<>()); return result; } backtracking(nums, 0); return result; } private void backtracking(int[] nums, int startIndex){ result.add(new ArrayList<>(path)); if (startIndex >= nums.length){ return; } for (int i = startIndex; i < nums.length; i++){ path.add(nums[i]); backtracking(nums, i + 1); path.removeLast(); } }}473. 火柴拼正方形 (medium)
- 思路 ：排序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};