目录引入约束型回溯是什么一、电话号码的字母组合每一层处理一个数字二、括号生成前缀不合法就不能继续三、目标和每个数字选择加号或减号四、字母大小写全排列字母两种选择数字一种选择五、N 皇后把每一行的列选择变成约束判断六、解数独在空格中尝试数字并恢复七、从多道约束题中归纳共同规律八、易错点九、本篇总结引入约束型回溯是什么回溯可以理解为在一棵选择树中不断尝试做出一个选择递归进入下一层返回后撤销选择再尝试其他选择。约束型回溯的特点是每一步都有比较明确的合法性限制很多无效分支在生成过程中就能被排除。path表示当前正在构造的字符串或数字选择ret表示保存的结果集合pos或index表示处理到输入的哪个位置left和right在括号题中表示已经使用的左右括号数量。棋盘题中常见的row和col分别表示行号和列号visited表示网格位置是否已经出现在当前路径中。一、电话号码的字母组合每一层处理一个数字题目描述题目电话号码的字母组合。LeetCode 17。数字 2 到 9 分别对应若干英文字母。给定一串数字返回按数字顺序拼接出的所有可能字母组合。例如数字23可以组成ad、ae、af等字符串。题目链接电话号码的字母组合算法原理输入字符串中的每个数字对应一组候选字母。递归的层数对应数字的位置每一层从当前数字对应的字母中选择一个加入正在构造的字符串下一层处理下一个数字。当pos digits.length()时说明每个数字都已经选过一个字母当前字符串就是一个完整答案。递归返回后删除最后添加的字符恢复到选择之前的状态。Java 代码class Solution { String[] hash { , , abc, def, ghi, jkl, mno, pqrs, tuv, wxyz }; ListString ret; StringBuffer path; public ListString letterCombinations(String digits) { ret new ArrayList(); path new StringBuffer(); if (digits.length() 0) return ret; dfs(digits, 0); return ret; } public void dfs(String digits, int pos) { if (pos digits.length()) { ret.add(path.toString()); return; } String cur hash[digits.charAt(pos) - 0]; for (int i 0; i cur.length(); i) { path.append(cur.charAt(i)); dfs(digits, pos 1); path.deleteCharAt(path.length() - 1); } } }代码说明hash是数字到字母字符串的对应表。digits.charAt(pos)取出当前位置的字符减去字符0后得到对应的数组下标。StringBuffer是可以修改内容的字符串类型。append在末尾添加字符递归返回后用deleteCharAt删除最后一个字符。这里不需要visited因为每个数字位置只处理一次。二、括号生成前缀不合法就不能继续题目描述题目括号生成。LeetCode 22。给定n对括号生成所有由n个左括号和n个右括号组成、并且括号能够正确匹配的字符串。题目链接括号生成算法原理每一步有两个候选添加左括号或添加右括号。左括号总数不能超过n右括号只有在数量小于左括号时才能添加因为任何前缀中右括号都不能多于左括号。这个限制让非法字符串在生成阶段就被排除。例如还没有出现左括号时不能直接添加右括号。right n时所有右括号都已经使用当前路径一定是完整答案。Java 代码class Solution { int left; int right; int n; StringBuffer path; ListString ret; public ListString generateParenthesis(int _n) { n _n; left 0; right 0; path new StringBuffer(); ret new ArrayList(); dfs(); return ret; } public void dfs() { if (right n) { ret.add(path.toString()); return; } if (left n) { path.append((); left; dfs(); path.deleteCharAt(path.length() - 1); left--; } if (right left) { path.append()); right; dfs(); path.deleteCharAt(path.length() - 1); right--; } } }代码说明left和right分别记录当前已经添加的左右括号数量。添加左括号后递归返回时要同时删除字符并让left--因为这两步共同恢复了当前层的状态。添加右括号的条件是right left。这不是为了最后再检查字符串而是保证搜索过程中每一个前缀都可能成为合法括号串。三、目标和每个数字选择加号或减号题目描述题目目标和。LeetCode 494。给定一个整数数组在每个数字前添加或-使表达式计算结果等于目标值。返回满足条件的表达式数量。题目链接目标和算法原理递归处理数组下标pos。当前数字有两种选择加上它或者减去它。走到数组末尾时如果累计结果等于目标值就找到一种方案。这道题只需要统计数量不需要保存具体路径所以递归方法可以直接返回方案数。加号分支和减号分支的返回值相加就是当前状态的总方案数。Java 代码class Solution { public int findTargetSumWays(int[] nums, int target) { return dfs(nums, 0, 0, target); } private int dfs(int[] nums, int pos, int sum, int target) { if (pos nums.length) { return sum target ? 1 : 0; } int add dfs(nums, pos 1, sum nums[pos], target); int subtract dfs(nums, pos 1, sum - nums[pos], target); return add subtract; } }代码说明pos表示当前处理到哪个数字sum表示前面已经选择符号后得到的累计结果。每一层都固定产生两个递归调用一个选择加号一个选择减号。到达数组末尾时sum target返回 1表示找到一种方案否则返回 0。这里没有path和ret列表是因为题目只要求数量不要求列出每种表达式。四、字母大小写全排列字母两种选择数字一种选择题目描述题目字母大小写全排列。LeetCode 784。给定一个由字母和数字组成的字符串把其中的每个字母分别变成小写或大写返回所有可能的字符串。数字保持不变。题目链接字母大小写全排列算法原理递归处理字符串中的一个字符。如果当前字符是数字只有保留原字符这一条分支如果是字母就产生小写和大写两条分支。处理完成后返回字符串末尾删除当前字符。合法性约束在这里很简单数字不能被改成字母字母只能在大小写两种状态中选择。Java 代码class Solution { public ListString letterCasePermutation(String s) { ListString ret new ArrayList(); StringBuffer path new StringBuffer(); dfs(s, 0, path, ret); return ret; } private void dfs(String s, int pos, StringBuffer path, ListString ret) { if (pos s.length()) { ret.add(path.toString()); return; } char current s.charAt(pos); if (Character.isDigit(current)) { path.append(current); dfs(s, pos 1, path, ret); path.deleteCharAt(path.length() - 1); return; } path.append(Character.toLowerCase(current)); dfs(s, pos 1, path, ret); path.deleteCharAt(path.length() - 1); path.append(Character.toUpperCase(current)); dfs(s, pos 1, path, ret); path.deleteCharAt(path.length() - 1); } }代码说明Character.isDigit判断当前字符是否为数字Character.toLowerCase和Character.toUpperCase分别把字母转换为小写和大写。当前字符是数字时只递归一次当前字符是字母时递归两次。每次追加字符后都要在返回时删除最后一个字符这样下一条分支使用的仍然是同一个长度的前缀。五、N 皇后把每一行的列选择变成约束判断题目描述题目N 皇后。LeetCode 51。在n * n的棋盘上放置n个皇后使任意两个皇后都不在同一列、同一条主对角线或同一条副对角线上。返回所有合法棋盘布局。题目链接N 皇后算法原理可以按行放置皇后每一行只放一个。进入某一行后依次尝试每一列。若该列或两条对角线已经有皇后当前选择不合法直接跳过。columns[col]记录列是否被占用。主对角线可以用row - col n - 1编号副对角线可以用row col编号。放置皇后后递归下一行返回时恢复棋盘和三个标记。Java 代码class Solution { public ListListString solveNQueens(int n) { ListListString ret new ArrayList(); char[][] board new char[n][n]; for (char[] row : board) { Arrays.fill(row, .); } boolean[] columns new boolean[n]; boolean[] mainDiagonal new boolean[2 * n - 1]; boolean[] antiDiagonal new boolean[2 * n - 1]; dfs(0, n, board, columns, mainDiagonal, antiDiagonal, ret); return ret; } private void dfs(int row, int n, char[][] board, boolean[] columns, boolean[] mainDiagonal, boolean[] antiDiagonal, ListListString ret) { if (row n) { ListString solution new ArrayList(); for (char[] currentRow : board) { solution.add(new String(currentRow)); } ret.add(solution); return; } for (int col 0; col n; col) { int main row - col n - 1; int anti row col; if (columns[col] || mainDiagonal[main] || antiDiagonal[anti]) { continue; } board[row][col] Q; columns[col] true; mainDiagonal[main] true; antiDiagonal[anti] true; dfs(row 1, n, board, columns, mainDiagonal, antiDiagonal, ret); board[row][col] .; columns[col] false; mainDiagonal[main] false; antiDiagonal[anti] false; } } }代码说明row表示当前正在放置皇后的行。Arrays.fill(row, .)把棋盘每一行初始化为空位Arrays是 Java 数组工具类fill用于把数组元素填成同一个值。一旦某个位置合法就把棋盘改为Q并把列和两条对角线标记为已占用。递归返回后必须四项全部恢复否则下一种列选择会受到上一条分支影响。保存答案时逐行创建新的String不能直接保存仍会继续修改的char[][] board。六、解数独在空格中尝试数字并恢复题目描述题目解数独。LeetCode 37。给定一个部分填写的数独棋盘空白位置用.表示。要求填入数字 1 到 9使每一行、每一列和每个3 * 3小方格中的数字都不重复。题目链接解数独算法原理从左到右、从上到下寻找空格。对每个空格依次尝试字符1到9只有不违反行、列和小方格规则时才放入。继续搜索下一个空格如果后面无法完成就把当前空格恢复为.再尝试下一个数字。当所有位置都处理完时说明找到完整答案。这里的合法性判断就是剪枝恢复空格就是回溯。Java 代码class Solution { public void solveSudoku(char[][] board) { dfs(board, 0, 0); } private boolean dfs(char[][] board, int row, int col) { if (row 9) return true; if (col 9) return dfs(board, row 1, 0); if (board[row][col] ! .) { return dfs(board, row, col 1); } for (char value 1; value 9; value) { if (!isValid(board, row, col, value)) { continue; } board[row][col] value; if (dfs(board, row, col 1)) { return true; } board[row][col] .; } return false; } private boolean isValid(char[][] board, int row, int col, char value) { for (int i 0; i 9; i) { if (board[row][i] value) return false; if (board[i][col] value) 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] value) return false; } } return true; } }代码说明dfs返回布尔值true表示从当前位置开始能够完成数独false表示当前尝试失败。遇到已有数字就跳到下一个位置遇到空格就尝试 1 到 9。如果放入某个数字后递归成功直接返回true如果失败就把当前位置恢复为.。isValid分别检查当前行、当前列和所在的3 * 3小方格。七、从多道约束题中归纳共同规律电话号码组合、括号生成和大小写排列的共同点是每一层都有有限的候选字符但候选数量会因为题目约束不同而变化。数字对应多个字母括号受到左右数量限制大小写题中数字只有一个候选而字母有两个候选。N 皇后和数独的候选也是逐步尝试但合法性判断更复杂。它们都不是先生成所有布局再检查而是在准备做选择时就判断列、对角线、行、列和小方格是否冲突。因此约束型回溯的稳定结构是确定当前处理位置列出当前位置的候选先判断候选是否合法合法才修改状态并递归递归失败后恢复状态。约束越早检查越能减少无效分支。八、易错点括号生成只限制左括号数量没有限制right left。字符或括号追加后没有删除导致后续分支带着旧内容。数独失败后没有把空格恢复为.。N 皇后只检查列没有检查主对角线和副对角线。保存棋盘答案时直接保存可变数组回溯后已经保存的结果被修改。网格或棋盘访问前没有先判断是否越界。对只要求统计数量的题强行保存所有路径增加了不必要的状态。九、本篇总结约束型回溯不是换了一套完全不同的算法而是在普通回溯的“做选择、递归、撤销选择”之间增加合法性判断。判断一个新题时可以先确定每一层处理什么再列出候选选择最后把题目规则翻译成if条件。只要状态修改和恢复严格配对代码就不容易被不同分支互相污染。