# Subsets and Permutations

Posted by chunyang on May 11, 2019

### 题目

#### Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

#### Permutation

Given a collection of distinct integers, return all possible permutations.

### 解法

• 组合：2^n
• 排列：n!

#### 思路

[], [1], [2], [1,2]

• 取当前元素
• 不取当前元素

• 不取，直接跳过这个 bag
• 取，挨个取

1, 2, 3, 1, 3, 2, 2, 1, 3, 2, 3, 1, 3, 2, 1, 3, 1, 2

#### 代码


class Solution {
private:
void subsets(vector<int>& nums, vector<vector<int>>& result, vector<int>& cur, int k, int pos) {
if (cur.size() == k) {
result.push_back(cur);
return;
}
int size = nums.size();
for (int i = pos; i < size; ++i) {
cur.push_back(nums[i]);
subsets(nums, result, cur, k, i+1);
cur.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int> > result;
int size = nums.size();
result.emplace_back(vector<int>());
vector<int> cur;
for (int i = 1; i <= size; ++i) {
subsets(nums, result, cur, i, 0);
}
return result;
}
};

class Solution {
typedef vector<vector<int>> VV;
typedef map<int, int> Bag;
private:
void subsets(Bag& bags, VV& result, vector<int>& cur, int k) {

if (cur.size() == k) {
result.push_back(cur);
return;
}

if (bags.empty()) return;
auto iter = bags.begin();
int bag_num = (*iter).first;
int bag_size = (*iter).second;
bags.erase(iter);

// with current bag;
int i = 0;
for (; i < bag_size;) {
cur.push_back(bag_num);
++i;
if (cur.size() > k) break;
subsets(bags, result, cur, k);
}

// without current bag;
cur.resize(cur.size() - i);
subsets(bags, result, cur, k);

bags[bag_num] = bag_size;

}
public:
vector<vector<int>> subsets(vector<int>& nums) {
VV result;
result.emplace_back(vector<int>());
vector<int> cur;

// build bag
map<int, int> bags;
for(auto num: nums) {
bags[num]++;
}
int size = nums.size();
for (int i = 1; i <= size; ++i) {
subsets(bags, result, cur, i);
}
return result;
}
};


class Solution {
public:
typedef vector<vector<int> > VV;
typedef vector<int> V;

private:
void permute(V& nums, VV& result, int start) {
int size = nums.size();
if (start == size) {
result.push_back(nums);
return;
}
for (int i = start; i < size; ++i) {
swap(nums[start], nums[i]);
permute(nums, result, start + 1);
swap(nums[i], nums[start]);
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
VV result;
permute(nums, result, 0);
return result;
}
};

class Solution {
public:
typedef vector<int> V;
typedef vector<V> VV;
typedef set<int> Set;

private:
void permuteUnique(V& nums, VV& result, int start) {
int size = nums.size();
if (start == size) {
result.push_back(nums);
return;
}
Set s;
for (int i = start; i < size; ++i) {
if (s.insert(nums[i]).second) {
swap(nums[i], nums[start]);
permuteUnique(nums, result, start + 1);
swap(nums[i], nums[start]);
}
}
}

public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
VV result;
permuteUnique(nums, result, 0);
return result;
}
};