给定一个没有重复数字的序列，返回其所有可能的全排列。
示例:
输入: [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 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划。而今天的两个问题，都没有重叠子问题，也就是回溯算法问题了，复杂度非常高是不可避免的。
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/17559.html