1、获取全排列
https://leetcode.com/problems/permutations/submissions/
按字典序输出：
这里用的是vector<int>，不是引用、指针，也就是说深层次中的递归不会影响到前面层vector中的数据。
class Solution {
public:
vector<vector<int>>ans;
void dfs(vector<int>arr, int k, int n) {
if (k == n) {
ans.push_back(arr);
return;
}
for (int i = k; i < n; i++) {
swap(arr[i], arr[k]);
dfs(arr, k + , n);
}
}
vector<vector<int>> permute(vector<int>& nums) {
//sort(nums.begin(), nums.end()); //如果输入顺序是非字典序，那么就一定要先排序一次。为了dfs中的 i = k ~ n 的循环，swap(arr[i],arr[k])，得到的 n-k 个序列是满足字典升序的。
dfs(nums, , nums.size());
return ans;
}
};
这是算法教材书上的写法，理论上引用是会快一点的，这个vector<int>&arr也可以直接用int数组，这题数据量比较小，体现不出来。但是输出顺序非常之古怪，慎用。
class Solution {
public:
vector<vector<int>>ans;
void dfs(vector<int>&arr, int k, int n) {
if (k == n) {
ans.push_back(arr);
return;
}
for (int i = k; i < n; i++) {
swap(arr[i], arr[k]);
dfs(arr, k + , n);
swap(arr[i], arr[k]);
}
}
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums, , nums.size());
return ans;
}
};
2、输出不重复的排列方式
https://leetcode.com/problems/permutations-ii/
深搜去重:
DFS中，如果第i个和第k个是相同的，就不往下进行搜索了，去除掉了出现重复的可能性。
class Solution {
public:
vector<vector<int>> ans;
void dfs(vector<int> nums, int n, int k) {
if (k == n) {
ans.push_back(nums);
return;
}
for (int i = k; i < n; ++i) {
if (i != k && nums[i] == nums[k]) continue;
swap(nums[k], nums[i]);
dfs(nums, n, k + );
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());
dfs(nums, nums.size(), );
return ans;
}
};
STL: next_permutation
next_permutation: 对于给定的任意一种全排列，给出能求出下一个全排列的情况。默认不会有重复序列出现的。
如果仍然有下一个全排列，返回true，给出下一个全排列；
否则返回false，给出第一个全排列；
因为可能出现的重复序列，让我们无法预知结果的个数，就必须先排序，从头做到尾。
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>>ans;
sort(nums.begin(), nums.end());
do {
ans.push_back(nums);
} while (next_permutation(nums.begin(), nums.end()));
return ans;
}
};
3、按字典序得到下一个全排列
https://leetcode.com/problems/next-permutation/submissions/
STL: next_permutation
这个题目，好像就是为next_permutation量身定做的一样。但其实效果比较一般。
class Solution {
public:
void nextPermutation(vector<int>& nums) {
next_permutation(nums.begin(), nums.end());
; i < nums.size(); i++) {
printf("%d ",nums[i]);
}
printf("\n");
}
};