正文
4、例题
（1）给定一个不含重复元素的整数数组，返回其所有可能的子集 | leetcode78
整个过程的决策树如图所示：
class Solution { public: vector<vector<int>> subsets(vector<int>& choices) { // 初始变量 vector<vector<int>> results; // 答案列表 vector<int> pathway; // 已走路径 int begin = 0; // 辅助变量，从辅助变量指定的索引开始遍历选择列表，避免重复选择 // 深度优先搜索 dfs(results, pathway, choices, begin); // 返回结果 return results; } void dfs( // 深度优先搜索 ( 回溯法 ) vector<vector<int>> & results, // 答案列表，函数不返回任何内容，而是直接更新答案列表 vector<int> & pathway, // 已走路径 vector<int> & choices, // 选择列表 int begin // 辅助变量，函数不修改选择列表，而是通过辅助变量判断选择是否合法 ) { // 若能符合结束条件 // 每个节点都是满足结束条件 results.push_back(pathway); // 则将已走路径加入答案列表 // 继续往下执行 // 遍历选择列表 for (int i = 0; i < choices.size(); i++) { // 若不符合约束条件 if (i < begin) { continue; // 则跳过该选择 } // 做出选择 pathway.push_back(choices[i]); // 递归调用 dfs(results, pathway, choices, i + 1); // 撤销选择 pathway.pop_back(); } } };
（2）给定一个含有重复元素的整数数组，返回其所有可能的子集 | leetcode90
与上题的不同之处仅仅在于数组含有重复元素，体现在解法上则有两个不同
一是需要先将数组排序，二是多了个约束条件，避免选择重复的元素而导致错误
class Solution { public: vector<vector<int>> subsetsWithDup(vector<int>& choices) { // 选择列表排序 sort(choices.begin(), choices.end()); // 不同之处 // 初始变量 vector<vector<int>> results; // 答案列表 vector<int> pathway; // 已走路径 int begin = 0; // 辅助变量，从辅助变量指定的索引开始遍历选择列表，避免重复选择 // 深度优先搜索 dfs(results, pathway, choices, begin); // 返回结果 return results; } void dfs( // 深度优先搜索 ( 回溯法 ) vector<vector<int>> & results, // 答案列表，函数不返回任何内容，而是直接更新答案列表 vector<int> & pathway, // 已走路径 vector<int> & choices, // 选择列表 int begin // 辅助变量，函数不修改选择列表，而是通过辅助变量判断选择是否合法 ) { // 若能符合结束条件 // 每个节点都是满足结束条件 results.push_back(pathway); // 则将已走路径加入答案列表 // 继续往下执行 // 遍历选择列表 for (int i = 0; i < choices.size(); i++) { // 若不符合约束条件 if ( i < begin || i > begin && choices[i] == choices[i - 1] // 不同之处 ) { continue; // 则跳过该选择 } // 做出选择 pathway.push_back(choices[i]); // 递归调用 dfs(results, pathway, choices, i + 1); // 撤销选择 pathway.pop_back(); } } };
（3）给定一个不含重复元素的整数数组和一个正整数 k，返回其所有可能的包含 k 个数字的组合
组合问题可以看作是子集问题的特例，它们的不同之仅在于结束条件
子集问题的结束条件是所有节点，组合问题的结束条件是当前节点的路径长度等于指定值
整个过程的决策树如图所示：
class Solution { public: vector<vector<int>> combine(vector<int>& choices, int k) { // 初始变量 vector<vector<int>> results; // 答案列表 vector<int> pathway; // 已走路径 int begin = 0; // 辅助变量，从辅助变量指定的索引开始遍历选择列表，避免重复选择 // 深度优先搜索 dfs(results, pathway, choices, begin, k); // 返回结果 return results; } void dfs( // 深度优先搜索 ( 回溯法 ) vector<vector<int>> & results, // 答案列表，函数不返回任何内容，而是直接更新答案列表 vector<int> & pathway, // 已走路径 vector<int> & choices, // 选择列表 int begin, // 辅助变量，函数不修改选择列表，而是通过辅助变量判断选择是否合法 int k ) { // 若能符合结束条件 if (pathway.size() == k) { results.push_back(pathway); // 则将已走路径加入答案列表 return; // 并且马上返回 } // 剪枝，如果删除掉，逻辑也是正确的，但效率较低 if (pathway.size() + choices.size() - begin < k) { return; } // 遍历选择列表 for (int i = 0; i < choices.size(); i++) { // 若不符合约束条件 if (i < begin) { continue; // 则跳过该选择 } // 做出选择 pathway.push_back(choices[i]); // 递归调用 dfs(results, pathway, choices, i + 1, k); // 撤销选择 pathway.pop_back(); } } };
4）给定一个含有重复元素的整数数组和一个正整数 k，返回其所有可能的包含 k 个数字的组合
与上题的不同之处仅仅在于数组含有重复元素，体现在解法上则有两个不同
一是需要先将数组排序，二是多了个约束条件，避免选择重复的元素而导致错误
class Solution { public: vector<vector<int>> combineUnique(vector<int>& choices, int k) { // 选择列表排序 sort(choices.begin(), choices.end()); // 不同之处 // 初始变量 vector<vector<int>> results; // 答案列表 vector<int> pathway; // 已走路径 int begin = 0; // 辅助变量，从辅助变量指定的索引开始遍历选择列表，避免重复选择 // 深度优先搜索 dfs(results, pathway, choices, begin, k); // 返回结果 return results; } void dfs( // 深度优先搜索 ( 回溯法 ) vector<vector<int>> & results, // 答案列表，函数不返回任何内容，而是直接更新答案列表 vector<int> & pathway, // 已走路径 vector<int> & choices, // 选择列表 int begin, // 辅助变量，函数不修改选择列表，而是通过辅助变量判断选择是否合法 int k ) { // 若能符合结束条件 if (pathway.size() == k) { results.push_back(pathway); // 则将已走路径加入答案列表 return; // 并且马上返回 } // 剪枝，如果删除掉，逻辑也是正确的，但效率较低 if (pathway.size() + choices.size() - begin < k) { return; } // 遍历选择列表 for (int i = 0; i < choices.size(); i++) { // 若不符合约束条件 if ( i < begin || i > begin && choices[i] == choices[i - 1] // 不同之处 ) { continue; // 则跳过该选择 } // 做出选择 pathway.push_back(choices[i]); // 递归调用 dfs(results, pathway, choices, i + 1, k); // 撤销选择 pathway.pop_back(); } } };
5）给定一个不含重复元素的整数数组，返回其所有可能的全排列 | leetcode46
整个过程的决策树如图所示：
class Solution { public: vector<vector<int>> permute(vector<int>& choices) { int n = choices.size(); // 初始变量 vector<vector<int>> results; // 答案列表 vector<int> pathway; // 已走路径 vector<bool> visited(choices.size(), false); // 辅助变量，表示对应的选择是否曾被使用过，避免重复选择 // 深度优先搜索 dfs(results, pathway, choices, visited, n); // 返回结果 return results; } void dfs( // 深度优先搜索 ( 回溯法 ) vector<vector<int>> & results, // 答案列表，函数不返回任何内容，而是直接更新答案列表 vector<int> & pathway, // 已走路径 vector<int> & choices, // 选择列表 vector<bool> & visited, // 辅助变量，函数不修改选择列表，而是通过辅助变量判断选择是否合法 int n ) { // 若能符合结束条件 if (pathway.size() == n) { results.push_back(pathway); // 则将已走路径加入答案列表 return; // 并且马上返回 } // 遍历选择列表 for (int i = 0; i < choices.size(); i++) { // 若不符合约束条件 if (visited[i] == true) { continue; // 则跳过该选择 } // 做出选择 pathway.push_back(choices[i]); visited[i] = true; // 递归调用 dfs(results, pathway, choices, visited, n); // 撤销选择 pathway.pop_back(); visited[i] = false; } } };
（6）给定一个含有重复元素的整数数组，返回其所有可能的全排列 | leetcode47
与上题的不同之处仅仅在于数组含有重复元素，体现在解法上则有两个不同
一是需要先将数组排序，二是多了个约束条件，避免选择重复的元素而导致错误
class Solution { public: vector<vector<int>> permuteUnique(vector<int>& choices) { int n = choices.size(); // 选择列表排序 sort(choices.begin(), choices.end()); // 不同之处 // 初始变量 vector<vector<int>> results; // 答案列表 vector<int> pathway; // 已走路径 vector<bool> visited(choices.size(), false); // 辅助变量，表示对应的选择是否曾被使用过，避免重复选择 // 深度优先搜索 dfs(results, pathway, choices, visited, n); // 返回结果 return results; } void dfs( // 深度优先搜索 ( 回溯法 ) vector<vector<int>> & results, // 答案列表，函数不返回任何内容，而是直接更新答案列表 vector<int> & pathway, // 已走路径 vector<int> & choices, // 选择列表 vector<bool> & visited, // 辅助变量，函数不修改选择列表，而是通过辅助变量判断选择是否合法 int n ) { // 若能符合结束条件 if (pathway.size() == n) { results.push_back(pathway); // 则将已走路径加入答案列表 return; // 并且马上返回 } // 遍历选择列表 for (int i = 0; i < choices.size(); i++) { // 若不符合约束条件 if ( visited[i] == true || i > 0 && choices[i] == choices[i - 1] && visited[i - 1] == false // 不同之处 ) { continue; // 则跳过该选择 } // 做出选择 pathway.push_back(choices[i]); visited[i] = true; // 递归调用 dfs(results, pathway, choices, visited, n); // 撤销选择 pathway.pop_back(); visited[i] = false; } } };
（7）八皇后
给定一个 n × n 的棋盘，要求将 n 个皇后放在棋盘上，使皇后彼此之间不能相互攻击
怎么样的皇后会相互攻击呢？题目规定同一行、同一列、同一斜线上的皇后会相互攻击
要求返回所有解决方案，用二维字符串数组表示，其中 . 表示空位，Q 表示皇后 | leetcode51
class Solution { public: vector<vector<string>> solveNQueens(int n) { // 初始变量 vector<vector<string>> results; vector<string> pathway; for (int i = 0; i < n; i++) { pathway.push_back(string(n, '.')); } // 深度优先搜索 dfs(results, pathway, 0, n); // 返回结果 return results; } void dfs( vector<vector<string>> & results, // 答案列表 vector<string> & pathway, // 已走路径，实际上整个矩阵已经初始化，r 之前的行已放置皇后，r 之后的行未放置皇后 int r, // 当前处理行数 int n // 矩阵行列数量 ) { // 若能符合结束条件 // 即处理到最后一行 if (r == n) { results.push_back(pathway); // 则将已走路径加入答案列表 return; // 并且立即返回 } // 遍历选择列表 // 即逐一尝试在当前行的每一列放置皇后 for (int c = 0; c < n; c++) { // 若不符合约束条件 // 即每一行、每一列、每一斜线上最多只有一个皇后 // 实际上就是判断在当前行当前列放置皇后是否合法 if (!isValid(pathway, r, c, n)) { continue; // 则跳过该选择 } // 做出选择 // 在当前行当前列放置皇后 pathway[r][c] = 'Q'; // 递归调用 // 即处理下一行，需要传入下一状态对应的参数 dfs(results, pathway, r + 1, n); // 撤销选择 // 已走路径还需要恢复原样 pathway[r][c] = '.'; } } // 判断在 i 行 j 列放置皇后是否合法 bool isValid( vector<string>& pathway, int i, // 当前行 int j, // 当前列 int n // 矩阵行列数量 ) { for (int k = 0; k < n; k++) { // 当前行是否已经有皇后，若有，则返回不合法 if (pathway[i][k] == 'Q') return false; // 当前列是否已经有皇后，若有，则返回不合法 if (pathway[k][j] == 'Q') return false; // 斜线上是否已经有皇后，若有，则返回不合法 if (i + k < n && j + k < n && pathway[i + k][j + k] == 'Q') return false; if (i + k < n && j - k >= 0 && pathway[i + k][j - k] == 'Q') return false; if (i - k >= 0 && j + k < n && pathway[i - k][j + k] == 'Q') return false; if (i - k >= 0 && j - k >= 0 && pathway[i - k][j - k] == 'Q') return false; } // 若都没有，则返回合法 return true; } };
实际上，判断在当前行当前列放置皇后是否合法有更高效的方法，那就是使用哈希映射
使用四个哈希数组分别记录在哪一行、哪一列、哪一主对角线、哪一副对角线上已放置皇后
class Solution { public: vector<vector<string>> solveNQueens(int n) { // 初始变量 vector<vector<string>> results; vector<string> pathway; for (int i = 0; i < n; i++) { pathway.push_back(string(n, '.')); } bool* row = new bool[n](); // 记录哪一行已放置皇后，共有 n 行 bool* col = new bool[n](); // 记录哪一列已放置皇后，共有 n 列 bool* slash1 = new bool[2 * n - 1](); // 记录哪一主对角线（从左上到右下）已放置皇后，共有 2n - 1 个斜线 bool* slash2 = new bool[2 * n - 1](); // 记录哪一副对角线（从右上到左下）已放置皇后，共有 2n - 1 个斜线 // 深度优先搜索 dfs(results, pathway, 0, n, row, col, slash1, slash2); // 返回结果 return results; } void dfs( vector<vector<string>> & results, // 答案列表 vector<string> & pathway, // 已走路径，实际上整个矩阵已经初始化，r 之前的行已放置皇后，r 之后的行未放置皇后 int r, // 当前处理行数 int n, // 矩阵行列数量 bool* row, // 辅助变量，记录哪一行已放置皇后（不同之处） bool* col, // 辅助变量，记录哪一列已放置皇后（不同之处） bool* slash1, // 辅助变量，记录哪一主对角线已放置皇后（不同之处） bool* slash2 // 辅助变量，记录哪一副对角线已放置皇后（不同之处） ) { // 若能符合结束条件 // 即处理到最后一行 if (r == n) { results.push_back(pathway); // 则将已走路径加入答案列表 return; // 并且立即返回 } // 遍历选择列表 // 即逐一尝试在当前行的每一列放置皇后 for (int c = 0; c < n; c++) { // 若不符合约束条件 // 即每一行、每一列、每一斜线上最多只有一个皇后 if ( // （不同之处） row[r] == true || // 如果同一行已放置皇后 col[c] == true || // 如果同一列已放置皇后 slash1[r + c] == true || // 如果同一主对角线已放置皇后 slash2[r - c + n - 1] == true // 如果同一副对角线已放置皇后 ) { continue; // 则说明当前位置非法，跳过该选择 } // 做出选择 // 在当前行当前列放置皇后 // 同时更新对应的辅助变量（不同之处） pathway[r][c] = 'Q'; row[r] = true; col[c] = true; slash1[r + c] = true; slash2[r - c + n - 1] = true; // 递归调用 // 即处理下一行，需要传入下一状态对应的参数 dfs(results, pathway, r + 1, n, row, col, slash1, slash2); // 撤销选择 // 已走路径还需要恢复原样 // 同时还原对应的辅助变量（不同之处） pathway[r][c] = '.'; row[r] = false; col[c] = false; slash1[r + c] = false; slash2[r - c + n - 1] = false; } } };
考虑另一个变种问题，要求返回解决方案的数量，该如何设计呢 | leetcode52
class Solution { public: int totalNQueens(int n) { // 初始变量 vector<string> pathway; for (int i = 0; i < n; i++) { pathway.push_back(string(n, '.')); } bool* row = new bool[n](); bool* col = new bool[n](); bool* slash1 = new bool[2 * n - 1](); bool* slash2 = new bool[2 * n - 1](); // 深度优先搜索 // 此时函数不再通过修改传入的参数来得到答案，而是直接返回（不同之处） int ans = dfs(pathway, 0, n, row, col, slash1, slash2); // 返回结果 return ans; } int dfs( vector<string>& pathway, // 已走路径 int r, // 当前处理行数 int n, // 矩阵行列数量 bool* row, // 辅助变量，记录哪一行已放置皇后 bool* col, // 辅助变量，记录哪一列已放置皇后 bool* slash1, // 辅助变量，记录哪一主对角线已放置皇后 bool* slash2 // 辅助变量，记录哪一副对角线已放置皇后 ) { // 若能符合结束条件（base case） // 即处理到最后一行 if (r == n) { return 1; // 返回 1，表示得到 1 种可行解（不同之处） } // 记录可行解的数量（不同之处） int count = 0; // 遍历选择列表 for (int c = 0; c < n; c++) { if ( row[r] == true || // 如果同一行已放置皇后 col[c] == true || // 如果同一列已放置皇后 slash1[r + c] == true || // 如果同一主对角线已放置皇后 slash2[r - c + n - 1] == true // 如果同一副对角线已放置皇后 ) { continue; // 则说明当前位置非法，跳过该选择 } // 做出选择 // 在当前行当前列放置皇后 // 同时更新对应的辅助变量 pathway[r][c] = 'Q'; row[r] = true; col[c] = true; slash1[r + c] = true; slash2[r - c + n - 1] = true; // 递归调用 // 即处理下一行，需要传入下一状态对应的参数 // 当前节点可行解的数量等于其所有子节点可行解的数量之和（不同之处） count += dfs(pathway, r + 1, n, row, col, slash1, slash2); // 撤销选择 // 已走路径还需要恢复原样 // 同时还原对应的辅助变量 pathway[r][c] = '.'; row[r] = false; col[c] = false; slash1[r + c] = false; slash2[r - c + n - 1] = false; } // 返回可行解的数量（不同之处） return count; } };
（8）解数独
给定一个 9 × 9 的矩阵，矩阵中部分空格已填入数字，其余空格用 . 来表示 | leetcode37
题目保证输入数独有唯一解，最后数独解法需要遵循以下规则：
- 数字
1 ~ 9在每一行只能出现一次 - 数字
1 ~ 9在每一列只能出现一次 - 数字
1 ~ 9在图示3 × 3的九宫格内只能出现一次
class Solution { public: void solveSudoku(vector<vector<char>>& board) { dfs(board, 0, 0); } bool dfs( vector<vector<char>>& board, // 已走路径，实际上整个矩阵已经初始化 // 1、1 ~ i-1 行已处理完，i 行 1 ~ j-1 列已处理完 // 2、i+1 ~ 9 行还未处理，i 行 j+1 ~ 9 列还未处理 int i, // 当前行 int j // 当前列 ) { // 边界条件：行数超出边框 -> 说明找到一个可行解（base case） if (i == 9) { return true; } // 边界条件：列数超出边框 -> 换到下一行继续尝试 if (j == 9) { return dfs(board, i + 1, 0); } // 边界条件：框内已有数字 -> 继续尝试下一个位置 if (board[i][j] != '.') { return dfs(board, i, j + 1); } // 正常流程：框内没有数字 -> 逐一尝试可能的选择 for (char c = '1'; c <= '9'; c++) { // 如果不能填入 // 说明当前选择不可行，则继续尝试下一个选择 if (!isValid(board, i, j, c)) { continue; } // 如果可以填入 // 填入 board[i][j] = c; // 继续尝试填写下一个位置 // 如果后续填写都是可行的，直接返回，不要回退，否则会把矩阵还原 if (dfs(board, i, j + 1)) { return true; }; // 如果后续不行 // 还原 board[i][j] = '.'; } // 所有尝试都以失败告终 return false; } // 判断在 i 行 j 列填入字符 c 是否合法 bool isValid(vector<vector<char>>& board, int i, int j, char c) { for (int k = 0; k < 9; k++) { // 如果同一行有相同的数字，则不合法 if (board[i][k] == c) return false; // 如果同一列有相同的数字，则不合法 if (board[k][j] == c) return false; // 如果同一九宫格有相同的数字，则不合法 if (board[(i / 3) * 3 + k / 3][(j / 3) * 3 + k % 3] == c) return false; } // 如果没有出现上述情况，则合法 return true; } };
同样的，我们可以使用哈希映射加速判断在当前行当前列中填写某个字符是否合法
使用三个哈希数组分别记录每行、每列、每宫格中每个数字是否出现，这是典型的以空间换时间
class Solution { public: void solveSudoku(vector<vector<char>>& board) { // 初始变量 bool row[9][9] = {false}; // 记录每行中数字 1 ~ 9 是否出现，共有 9 行，每行中有 9 个数字 bool col[9][9] = {false}; // 记录每列中数字 1 ~ 9 是否出现，共有 9 列，每列中有 9 个数字 bool box[9][9] = {false}; // 记录每宫格数字 1 ~ 9 是否出现，共有 9 个宫格，每宫格有 9 个数字 for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] == '.') { continue; } else { int k = (i / 3) * 3 + (j / 3); int n = board[i][j] - '0' - 1; row[i][n] = true; // 数字 n 出现在第 i 行 col[j][n] = true; // 数字 n 出现在第 j 列 box[k][n] = true; // 数字 n 出现在第 k 个宫格 } } } dfs(board, 0, 0, row, col, box); } bool dfs( vector<vector<char>>& board, // 已走路径，实际上整个矩阵已经初始化 int i, // 当前行 int j, // 当前列 bool row[9][9], // 辅助变量，记录每行中数字 1 ~ 9 是否出现（不同之处） bool col[9][9], // 辅助变量，记录每列中数字 1 ~ 9 是否出现（不同之处） bool box[9][9] // 辅助变量，记录每宫格数字 1 ~ 9 是否出现（不同之处） ) { // 边界条件：行数超出边框 -> 说明找到一个可行解（base case） if (i == 9) { return true; } // 边界条件：列数超出边框 -> 换到下一行继续尝试 if (j == 9) { return dfs(board, i + 1, 0, row, col, box); } // 边界条件：框内已有数字 -> 继续尝试下一个位置 if (board[i][j] != '.') { return dfs(board, i, j + 1, row, col, box); } // 正常流程：框内没有数字 -> 逐一尝试可能的选择 for (char c = '1'; c <= '9'; c++) { int k = (i / 3) * 3 + (j / 3); int n = c - '0' - 1; // 如果不能填入 // 说明当前选择不可行，则继续尝试下一个选择 if (row[i][n] || col[j][n] || box[k][n]) { // （不同之处） continue; } // 如果可以填入 // 填入，同时要更新辅助变量（不同之处） board[i][j] = c; row[i][n] = true; col[j][n] = true; box[k][n] = true; // 继续尝试填写下一个位置 // 如果后续填写都是可行的，直接返回，不要回退，否则会把矩阵还原 if (dfs(board, i, j + 1, row, col, box)) { return true; }; // 如果后续不行 // 还原，同时要还原辅助变量（不同之处） board[i][j] = '.'; row[i][n] = false; col[j][n] = false; box[k][n] = false; } // 所有尝试都以失败告终 return false; } };
（9）括号生成
给定数字 n 代表生成括号的数量，要求返回所有有效的括号组合 | leetcode22
class Solution { public: vector<string> generateParenthesis(int n) { // 初始变量 vector<string> results; string pathway; // 深度优先搜索 dfs(results, pathway, n, n, n * 2); // 返回结果 return results; } void dfs( vector<string> & results, // 答案列表 string & pathway, // 已走路径，即当前括号组合 int lNum, // 左括号剩余个数 int rNum, // 右括号剩余个数 int aNum // 总括号数量 ) { // 若能符合结束条件 // 即当前括号组合已用完所有括号 if (pathway.size() == aNum) { results.push_back(pathway); // 则将已走路径加入答案列表 return; // 并且立即返回 } // 遍历选择列表 // 因为这里判断选择是否合法的逻辑稍有不同，所以没用循环，而是分开来写 // 若左括号还有剩余，则尝试放入左括号 if (lNum > 0) { // 做出选择 pathway.push_back('('); // 递归调用 dfs(results, pathway, lNum - 1, rNum, aNum); // 撤销选择 pathway.pop_back(); } // 若剩余右括号数量大于剩余左括号数量，则尝试放入右括号 if (lNum < rNum) { // 做出选择 pathway.push_back(')'); // 递归调用 dfs(results, pathway, lNum, rNum - 1, aNum); // 撤销选择 pathway.pop_back(); } } };
