回溯的本质是穷举,穷举所有可能,然后选出想要的答案 ,如果想让回溯法高效一些,需要进行剪枝 操作。
回溯法,一般可以解决如下几种问题:
组合问题:N 个数里面按一定规则找出 k 个数的集合
切割问题:一个字符串按一定规则有几种切割方式
子集问题:一个 N 个数的集合里有多少符合条件的子集
排列问题:N 个数按一定规则全排列,有几种排列方式
棋盘问题:N 皇后,解数独等等
组合不强调元素顺序,排列强调元素顺序 :
即 不同顺序的同样元素集合 算作排列,但不算组合
前言 看到回溯,感觉和 DFS(深度优先搜索)区别不太大,两者其实是包含关系。
回溯搜索是 DFS 的一种,对于某一个搜索树来说(搜索树记录路径和状态判断),其主要的区别是:
回溯法在求解过程中不保留完整的树结构,而深度优先搜索则记下完整的搜索树
为了减少存储空间,在深度优先搜索中,用标志的方法记录访问过的状态,这种方法使得深度优先搜索法与回溯法没什么区别
组合问题
N 个数里面按一定规则找出 k 个数的集合。
直接 DFS 暴搜,如果满足条件返回,再加上适当剪枝即可。
如果是一个集合来求组合的话,就需要 startIndex,例如:回溯算法:求组合问题! (opens new window) ,回溯算法:求组合总和! (opens new window) 。 如果是多个集合取组合,各个集合之间相互不影响,那么就不用 startIndex,例如:回溯算法:电话号码的字母组合
例题:77. 组合 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public : vector<vector<int >> ans; vector<int > tmp; void dfs (int n, int k, int idx) { if (tmp.size () == k) { ans.push_back (tmp); return ; } for (int i = idx; i <= n - (k - tmp.size ()) + 1 ; i++) { tmp.push_back (i); dfs (n, k, i + 1 ); tmp.pop_back (); } } vector<vector<int >> combine (int n, int k) { dfs (n, k, 1 ); return ans; } };
切割问题
一个字符串按一定规则有几种切割方式
具体算法类似组合问题,判断函数比较复杂。
例题:131. 分割回文串 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public : vector<vector<string>> ans; vector<string> tmp; bool check (string s, int start, int end) { for (int i = start, j = end; i < j; i++, j--) { if (s[i] != s[j]) return false ; } return true ; } void dfs (string s, int idx) { if (idx >= s.size ()) { ans.push_back (tmp); return ; } for (int i = idx; i < s.size (); i++) { if (!check (s, idx, i)) continue ; tmp.push_back (s.substr (idx, i - idx + 1 )); dfs (s, i + 1 ); tmp.pop_back (); } } vector<vector<string>> partition (string s) { dfs (s, 0 ); return ans; } };
子集问题
一个 N 个数的集合里有多少符合条件的子集
如果把 子集问题、组合问题、分割问题都抽象为一棵树的话,那么组合问题和分割问题都是收集树的叶子节点,而子集问题是找树的所有节点。
例题:78. 子集 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 class Solution { public : vector<vector<int >> ans; vector<int > tmp; void dfs (vector<int >& nums, int idx) { ans.push_back (tmp); if (idx >= nums.size ()) return ; for (int i = idx; i < nums.size (); i++) { tmp.push_back (nums[i]); dfs (nums, i + 1 ); tmp.pop_back (); } } vector<vector<int >> subsets (vector<int >& nums) { dfs (nums, 0 ); return ans; } };
排列问题
N 个数按一定规则全排列,有几种排列方式
排列是区分顺序的,不同顺序的集合算不同排列
和组合问题区别在每次循环的起始位置都是 0,同时用 vis 数组来记录状态。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public : vector<vector<int >> ans; vector<int > tmp; void dfs (vector<int >& nums, vector<bool >& vis) { if (tmp.size () == nums.size ()) { ans.push_back (tmp); return ; } for (int i = 0 ; i < nums.size (); i++) { if (vis[i]) continue ; tmp.push_back (nums[i]); vis[i] = true ; dfs (nums, vis); vis[i] = false ; tmp.pop_back (); } } vector<vector<int >> permute (vector<int >& nums) { vector<bool > vis (nums.size(), false ) ; dfs (nums, vis); return ans; } };
棋盘问题
N 皇后,解数独等等
给回溯函数加上 bool 返回值,找到一组成功解则返回。
例题:51. N 皇后 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 class Solution { public : vector<vector<string>> ans; void dfs (int row, int n, vector<string>& chess) { if (row == n) { ans.push_back (chess); return ; } for (int col = 0 ; col < n; col++) { if (check (row, col, n, chess)) { chess[row][col] = 'Q' ; dfs (row + 1 , n, chess); chess[row][col] = '.' ; } } } bool check (int row, int col, int n, vector<string>& chess) { for (int i = 0 ; i < row; i++) { if (chess[i][col] == 'Q' ) return false ; } for (int i = row - 1 , j = col - 1 ; i >= 0 && j >= 0 ; i--, j--) { if (chess[i][j] == 'Q' ) return false ; } for (int i = row - 1 , j = col + 1 ; i >= 0 && j < n; i--, j++) { if (chess[i][j] == 'Q' ) return false ; } return true ; } vector<vector<string>> solveNQueens (int n) { vector<string> chess (n, string(n, '.' )) ; dfs (0 , n, chess); return ans; } };
例题:37. 解数独 - 力扣(LeetCode)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 class Solution { public : bool check (int row, int col, int val, vector<vector<char >>& board) { for (int j = 0 ; j < 9 ; j++) { if (board[row][j] == val) return false ; } for (int i = 0 ; i < 9 ; i++) { if (board[i][col] == val) return false ; } int nRow = (row / 3 ) * 3 ; int nCol = (col / 3 ) * 3 ; for (int i = nRow; i < nRow + 3 ; i++) { for (int j = nCol; j < nCol + 3 ; j++) if (board[i][j] == val) return false ; } return true ; } bool dfs (vector<vector<char >>& board) { for (int i = 0 ; i < board.size (); i++) { for (int j = 0 ; j < board[0 ].size (); j++) { if (board[i][j] != '.' ) continue ; for (char k = '1' ; k <= '9' ; k++) { if (check (i, j, k, board)) { board[i][j] = k; if (dfs (board)) return true ; board[i][j] = '.' ; } } return false ; } } return true ; } void solveSudoku (vector<vector<char >>& board) { dfs (board); } };