给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
解:这道题时典型的回溯法,把所有可能的情况都尝试一遍;写代码的时候要注意做选择和撤销选择
class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> res; vector<int> vec_fuben=nums; AllPartion(res,vector<int>(),vec_fuben); return res; } void AllPartion(vector<vector<int>> &res,vector<int> tmp_vec,vector<int>vec_fuben) { if(vec_fuben.size()==0) { res.emplace_back(tmp_vec); return; } for(int i=0;i<vec_fuben.size();i++) { tmp_vec.emplace_back(vec_fuben[i]); int tmp_value=vec_fuben[i]; //做选择 vec_fuben.erase(vec_fuben.begin()+i); AllPartion(res,tmp_vec,vec_fuben); //撤销选择 vec_fuben.insert(vec_fuben.begin()+i,tmp_value); tmp_vec.pop_back(); } } };
二。51n皇后问题
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
这个问题很经典了,简单解释一下:给你一个 N×N 的棋盘,让你放置 N 个皇后,使得它们不能互相攻击。
PS:皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。
这个问题本质上跟全排列问题差不多,决策树的每一层表示棋盘上的每一行;每个节点可以做出的选择是,在该行的任意一列放置一个皇后。
直接套用框架:
vector<vector<string>> res; /* 输入棋盘边长 n,返回所有合法的放置 */ vector<vector<string>> solveNQueens(int n) { // '.' 表示空,'Q' 表示皇后,初始化空棋盘。 vector<string> board(n, string(n, '.')); backtrack(board, 0); return res; } // 路径:board 中小于 row 的那些行都已经成功放置了皇后 // 选择列表:第 row 行的所有列都是放置皇后的选择 // 结束条件:row 超过 board 的最后一行 void backtrack(vector<string>& board, int row) { // 触发结束条件 if (row == board.size()) { res.push_back(board); return; } int n = board[row].size(); for (int col = 0; col < n; col++) { // 排除不合法选择 if (!isValid(board, row, col)) continue; // 做选择 board[row][col] = 'Q'; // 进入下一行决策 backtrack(board, row + 1); // 撤销选择 board[row][col] = '.'; } } /* 是否可以在 board[row][col] 放置皇后? */ bool isValid(vector<string>& board, int row, int col) { int n = board.size(); // 检查列是否有皇后互相冲突 for (int i = 0; i < n; i++) { if (board[i][col] == 'Q') return false; } // 检查右上方是否有皇后互相冲突 for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) { if (board[i][j] == 'Q') return false; } // 检查左上方是否有皇后互相冲突 for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == 'Q') return false; } return true; }
函数 backtrack 依然像个在决策树上游走的指针,通过 row 和 col 就可以表示函数遍历到的位置,通过 isValid 函数可以将不符合条件的情况剪枝:
另外,拓展一下,
有的时候,我们并不想得到所有合法的答案,只想要一个答案,怎么办呢?比如解数独的算法,找所有解法复杂度太高,只要找到一种解法就可以。
其实特别简单,只要稍微修改一下回溯算法的代码即可:
// 函数找到一个答案后就返回 true
bool backtrack(vector<string>& board, int row) {
// 触发结束条件
if (row == board.size()) {
res.push_back(board);
return true;
}
...
for (int col = 0; col < n; col++) {
...
board[row][col] = 'Q';
if (backtrack(board, row + 1))
return true;
board[row][col] = '.';
}
return false;
}
这样修改后,只要找到一个答案,for 循环的后续递归穷举都会被阻断。也许你可以在 N 皇后问题的代码框架上,稍加修改,写一个解数独的算法?
三、最后总结
回溯算法就是个多叉树的遍历问题,关键就是在前序遍历和后序遍历的位置做一些操作,算法框架如下:
def backtrack(...):
for 选择 in 选择列表:
做选择
backtrack(...)
撤销选择
写 backtrack 函数时,需要维护走过的「路径」和当前可以做的「选择列表」,当触发「结束条件」时,将「路径」记入结果集。
其实想想看,回溯算法和动态规划是不是有点像呢?我们在动态规划系列文章中多次强调,动态规划的三个需要明确的点就是「状态」「选择」和「base case」,是不是就对应着走过的「路径」,当前的「选择列表」和「结束条件」?
某种程度上说,动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质,可以用 dp table 或者备忘录优化,将递归树大幅剪枝,这就变成了动态规划。而今天的两个问题,都没有重叠子问题,也就是回溯算法问题了,复杂度非常高是不可避免的。