#include <iostream>
#include <vector>
using namespace std;
// 子集
/*
思路：（深度优先遍历）
（1）子集表示不存在元素的先后顺序，并且要注意任意子集都包含空子集；
（2）k是要遍历的元素下标，是temp即将要加入的元素，然后后面的子集要从
*/
void subset(const vector<int> &arr, vector<vector<int>> &res, vector<int> &temp, int k)
{
res.push_back(temp);
for(int i = k; i < arr.size(); ++i) {
temp.push_back(arr[i]);
subset(arr, res, temp, i + 1); // 该位置容易错，容易写成 k + 1
temp.pop_back();
}
}
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
// 全排列
void permutation(vector<int> &arr, vector<vector<int>> &res, int k)
{
if(k == arr.size() -1) {
res.push_back(arr);
return;
} else {
for(int i = k; i < arr.size(); ++i) {
swap(arr[i], arr[k]);
permutation(arr, res, k + 1);
swap(arr[i], arr[k]);
}
}
}
int main() {
int len;
vector<int> arr;
cin>>len;
for(int i = 0; i < len; ++i) {
int temp;
cin>>temp;
arr.push_back(temp);
}
vector<vector<int>> res;
vector<int> temp;
// subset(arr, res, temp, 0); // 子集
permutation(arr, res, 0);
for(int i = 0; i < res.size(); ++i) {
for(int j = 0; j < res[i].size(); ++j) {
cout<<res[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
子集输出
1
1 2
1 2 3
1 3
2
2 3
3
全排列输出
1 2 3
1 3 2
2 1 3
2 3 1
3 2 1
3 1 2
存在重复数字的全排列
class Solution {
public:
vector<vector<int>> re;
vector<vector<int>> permuteUnique(vector<int>& nums) {
if(nums.size() == 0) return re;
func(nums, 0);
return re;
}
void swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}
void func(vector<int>& nums, int k) {
unordered_set<int> _set; // 关键数据结构，用于记录该位置上出现过的所有数字
if(k == nums.size() - 1)
re.push_back(nums);
else {
for(int i = k; i < nums.size(); ++i) {
if(_set.count(nums[i]) > 0) {
// 证明该位置已经出现过同样的数字了，不用进行后面的操作
continue;
}
_set.insert(nums[i]); // 如果该位置上面没有出现过该数字，则记录
swap(nums[k], nums[i]);
func(nums, k + 1);
swap(nums[k], nums[i]);
}
}
}
};
给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。
按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：
"123"
"132"
"213"
"231"
"312"
"321"
给定 n 和 k，返回第 k 个排列。
说明：
给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。
示例 1:
输入: n = 3, k = 3
输出: "213"
示例 2:
输入: n = 4, k = 9
输出: "2314"
代码：
/*
直接用回溯法做的话需要在回溯到第k个排列时终止就不会超时了, 但是效率依旧感人
可以用数学的方法来解, 因为数字都是从1开始的连续自然数, 排列出现的次序可以推
算出来, 对于n=4, k=15 找到k=15排列的过程:
1 + 对2,3,4的全排列 (3!个)
2 + 对1,3,4的全排列 (3!个) 3, 1 + 对2,4的全排列(2!个)
3 + 对1,2,4的全排列 (3!个)-------> 3, 2 + 对1,4的全排列(2!个)-------> 3, 2, 1 + 对4的全排列(1!个)-------> 3214
4 + 对1,2,3的全排列 (3!个) 3, 4 + 对1,2的全排列(2!个) 3, 2, 4 + 对1的全排列(1!个)
确定第一位:
k = 14(从0开始计数)
index = k / (n-1)! = 2, 说明第15个数的第一位是3
更新k
k = k - index*(n-1)! = 2
确定第二位:
k = 2
index = k / (n-2)! = 1, 说明第15个数的第二位是2
更新k
k = k - index*(n-2)! = 0
确定第三位:
k = 0
index = k / (n-3)! = 0, 说明第15个数的第三位是1
更新k
k = k - index*(n-3)! = 0
确定第四位:
k = 0
index = k / (n-4)! = 0, 说明第15个数的第四位是4
最终确定n=4时第15个数为3214
*/
class Solution {
public:
string getPermutation(int n, int k) {
string re = "";
int *num = new int[n];
num[0] = 1;
for(int i = 1; i < n; ++i) {
num[i] = num[i -1] * i;
}
list<int> _list;
for(int i = 0; i < n; ++i) {
_list.push_back(i + 1);
}
while(true) {
if(1 == k || _list.size() == 1) {
for(list<int>::iterator iter = _list.begin(); iter != _list.end(); ++iter)
re = re + to_string(*iter);
break;
}
int x = k / num[_list.size() - 1];
int y = k % num[_list.size() - 1];
if(y == 0) --x;
// cout<<"x = "<<x<<" y = "<<y<<endl;
list<int>::iterator iter = _list.begin();
advance(iter, x);
re = re + to_string(*iter);
// cout<<*iter<<endl;
k -= x * num[_list.size() - 1];
_list.erase(iter);
}
return re;
}
};
存在重复元素的子集
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
代码：
class Solution {
public:
// 利用set来去除重复元素
set<vector<int>> _set;
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int>> re;
if(nums.size() == 0) return re;
sort(nums.begin(), nums.end()); // 关键部分（先排序后可以避免重复的vector，eg: [1,4] 和 [4,1]）
vector<int> temp;
func(nums, temp, 0);
for(auto s : _set)
re.push_back(s);
return re;
}
void func(const vector<int>& nums, vector<int>& temp, int k) {
// sort(temp.begin(), temp.end());
// 在插入之前排序是错误的，因为后面temp.pop_back()的操作可能就不是我们插入的元素了。因为temp被排序了
_set.insert(temp);
for(int i = k; i < nums.size(); ++i) {
temp.push_back(nums[i]);
func(nums, temp, i + 1);
temp.pop_back();
}
}
};
网友评论