主要内容 #
- 全排列问题
- 求解方法
- 回溯三部曲
- 参考代码
1. 全排列问题 #
给定一个 没有重复 数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]
2. 求解方法 #
此时我们已经学习了组合问题、子集问题,接下来看一看排列问题。
相信这个排列问题就算是让你用for循环暴力把结果搜索出来,这个暴力也不是很好写。
所以正如我们在关于回溯算法,你该了解这些!所讲的为什么回溯法是暴力搜索,效率这么低,还要用它?
因为一些问题能暴力搜出来就已经很不错了!
我以[1,2,3]为例,抽象成树形结构如下:
3. 回溯三部曲 #
递归函数参数
首先排列是有序的,也就是说 [1,2] 和 [2,1] 是两个集合,这和之前分析的子集以及组合所不同的地方。
可以看出元素1在[1,2]中已经使用过了,但是在[2,1]中还要在使用一次1,所以处理排列问题就不用使用startIndex了。
但排列问题需要一个used数组,标记已经选择的元素,如上图中的橘黄色部分所示。
代码如下:
vector<vector<int>> result; vector<int> path; void backtracking (vector<int>& nums, vector<bool>& used)
递归终止条件
可以看出叶子节点,就是收割结果的地方。
那么什么时候,算是到达叶子节点呢?
当收集元素的数组path的大小达到和nums数组一样大的时候,说明找到了一个全排列,也表示到达了叶子节点。
代码如下:
// 此时说明找到了一组 if (path.size() == nums.size()) { result.push_back(path); return; }
单层搜索逻辑
这里和组合问题、子集问题最大的不同就是for循环里不用startIndex了。
因为排列问题,每次都要从头开始搜索,例如元素1在[1,2]中已经使用过了,但是在[2,1]中还要再使用一次1。
而used数组,其实就是记录此时path里都有哪些元素使用了,一个排列里一个元素只能使用一次。
代码如下:
for (int i = 0; i < nums.size(); i++) { if (used[i] == true) continue; // path里已经收录的元素,直接跳过 used[i] = true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] = false; }
4. 参考代码 #
#include<iostream> #include<vector> using namespace std; class Solution { public: vector<vector<int> > result; vector<int> path; void backtracking (vector<int>& nums, vector<bool>& used) { // 此时说明找到了一组 if (path.size() == nums.size()) { result.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { if (used[i] == true) continue; // path里已经收录的元素,直接跳过 used[i] = true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] = false; } } vector<vector<int> > permute(vector<int>& nums) { result.clear(); path.clear(); vector<bool> used(nums.size(), false); backtracking(nums, used); return result; } }; int main(){ vector<int> nums; int N, num; cin >> N; //输入集合的大小 while(N--){ cin >> num; //输入集合中的元素 nums.push_back(num); } vector<vector<int> > ans; //最终的集合 Solution solution; ans = solution.permute(nums); cout << endl; for(int i = 0; i < ans.size(); ++i){ for(int j = 0; j < ans[i].size(); ++j){ cout << ans[i][j] << " "; } cout << endl; } return 0; }