2014
11-18

# LeetCode-Subsets II[暴力枚举]

### Subsets II

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If S = [1,2,2], a solution is:

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

1. 递归

// LeetCode, Subsets II
// 增量构造法，版本1，时间复杂度O(2^n)，空间复杂度O(n)
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
sort(S.begin(), S.end());  // 必须排序

vector<vector<int> > result;
vector<int> path;

dfs(S, S.begin(), path, result);
return result;
}

private:
static void dfs(const vector<int> &S, vector<int>::iterator start,
vector<int> &path, vector<vector<int> > &result) {
result.push_back(path);

for (auto i = start; i < S.end(); i++) {
if (i != start && *i == *(i-1)) continue;
path.push_back(*i);
dfs(S, i + 1, path, result);
path.pop_back();
}
}
};

// LeetCode, Subsets II
// 增量构造法，版本2，时间复杂度O(2^n)，空间复杂度O(n)
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
vector<vector<int> > result;
sort(S.begin(), S.end()); // 必须排序

unordered_map<int, int> count_map; // 记录每个元素的出现次数
for_each(S.begin(), S.end(), [&count_map](int e) {
if (count_map.find(e) != count_map.end())
count_map[e]++;
else
count_map[e] = 1;
});

// 将map里的pair拷贝到一个vector里
vector<pair<int, int> > elems;
for_each(count_map.begin(), count_map.end(),
[&elems](const pair<int, int> &e) {
elems.push_back(e);
});
sort(elems.begin(), elems.end());
vector<int> path; // 中间结果

subsets(elems, 0, path, result);
return result;
}

private:
static void subsets(const vector<pair<int, int> > &elems,
size_t step, vector<int> &path, vector<vector<int> > &result) {
if (step == elems.size()) {
result.push_back(path);
return;
}

for (int i = 0; i <= elems[step].second; i++) {
for (int j = 0; j < i; ++j) {
path.push_back(elems[step].first);
}
subsets(elems, step + 1, path, result);
for (int j = 0; j < i; ++j) {
path.pop_back();
}
}
}
};

// LeetCode, Subsets II
// 位向量法，时间复杂度O(2^n)，空间复杂度O(n)
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
vector<vector<int> > result; // 必须排序
sort(S.begin(), S.end());
vector<int> count(S.back() - S.front() + 1, 0);
// 计算所有元素的个数
for (auto i : S) {
count[i - S[0]]++;
}

// 每个元素选择了多少个
vector<int> selected(S.back() - S.front() + 1, -1);

subsets(S, count, selected, 0, result);
return result;
}

private:
static void subsets(const vector<int> &S, vector<int> &count,
vector<int> &selected, size_t step, vector<vector<int> > &result) {
if (step == count.size()) {
vector<int> subset;
for(size_t i = 0; i < selected.size(); i++) {
for (int j = 0; j < selected[i]; j++) {
subset.push_back(i+S[0]);
}
}
result.push_back(subset);
return;
}

for (int i = 0; i <= count[step]; i++) {
selected[step] = i;
subsets(S, count, selected, step + 1, result);
}
}
};

2. 迭代

// LeetCode, Subsets II
// 增量构造法
// 时间复杂度O(2^n)，空间复杂度O(1)
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
sort(S.begin(), S.end()); // 必须排序
vector<vector<int> > result(1);

size_t previous_size = 0;
for (size_t i = 0; i < S.size(); ++i) {
const size_t size = result.size();
for (size_t j = 0; j < size; ++j) {
if (i == 0 || S[i] != S[i-1] || j >= previous_size) {
result.push_back(result[j]);
result.back().push_back(S[i]);
}
}
previous_size = size;
}
return result;
}
};

二进制法

// LeetCode, Subsets II
// 二进制法，时间复杂度O(2^n)，空间复杂度O(1)
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
sort(S.begin(), S.end()); // 必须排序
// 用 set 去重，不能用 unordered_set，因为输出要求有序
set<vector<int> > result;
const size_t n = S.size();
vector<int> v;

for (size_t i = 0; i < 1U << n; ++i) {
for (size_t j = 0; j < n; ++j) {
if (i & 1 << j)
v.push_back(S[j]);
}
result.insert(v);
v.clear();
}
vector<vector<int> > real_result;
copy(result.begin(), result.end(), back_inserter(real_result));
return real_result;
}
};

Java代码:

public class Solution {
public static List<List<Integer>> subsetsWithDup(int[] S) {
int all = 1 << S.length;
Arrays.sort(S);
List<List<Integer>> subsetsList = new ArrayList();
for (int i = 0; i < all; i++) {
int b = 1;
List<Integer> tmpList = new ArrayList();
for (int j = 0; j < S.length; j++) {
if ((i & b) != 0) {
}
b <<= 1;
}
if(subsetsList.contains(tmpList)) continue;
}
return subsetsList;
}
}

Subsets

1. 其实改车只是自慰，别人是看不见得。而且如果是真的的话你们看看凌哥改T2宝石是什么就知道了，还有用板车改T3速度能爆到几百？不过我还是很感谢凌哥的，为一些狗提供了骗钱的渠道。话说卡商店好像得变成女的吧…你怎么没有…还是说改进了？我现在飞车已卸载，改

2. 其实改车只是自慰，别人是看不见得。而且如果是真的的话你们看看凌哥改T2宝石是什么就知道了，还有用板车改T3速度能爆到几百？不过我还是很感谢凌哥的，为一些狗提供了骗钱的渠道。话说卡商店好像得变成女的吧…你怎么没有…还是说改进了？我现在飞车已卸载，改

3. 其实改车只是自慰，别人是看不见得。而且如果是真的的话你们看看凌哥改T2宝石是什么就知道了，还有用板车改T3速度能爆到几百？不过我还是很感谢凌哥的，为一些狗提供了骗钱的渠道。话说卡商店好像得变成女的吧…你怎么没有…还是说改进了？我现在飞车已卸载，改

4. 其实改车只是自慰，别人是看不见得。而且如果是真的的话你们看看凌哥改T2宝石是什么就知道了，还有用板车改T3速度能爆到几百？不过我还是很感谢凌哥的，为一些狗提供了骗钱的渠道。话说卡商店好像得变成女的吧…你怎么没有…还是说改进了？我现在飞车已卸载，改

5. 其实改车只是自慰，别人是看不见得。而且如果是真的的话你们看看凌哥改T2宝石是什么就知道了，还有用板车改T3速度能爆到几百？不过我还是很感谢凌哥的，为一些狗提供了骗钱的渠道。话说卡商店好像得变成女的吧…你怎么没有…还是说改进了？我现在飞车已卸载，改

6. 其实改车只是自慰，别人是看不见得。而且如果是真的的话你们看看凌哥改T2宝石是什么就知道了，还有用板车改T3速度能爆到几百？不过我还是很感谢凌哥的，为一些狗提供了骗钱的渠道。话说卡商店好像得变成女的吧…你怎么没有…还是说改进了？我现在飞车已卸载，改

7. 其实改车只是自慰，别人是看不见得。而且如果是真的的话你们看看凌哥改T2宝石是什么就知道了，还有用板车改T3速度能爆到几百？不过我还是很感谢凌哥的，为一些狗提供了骗钱的渠道。话说卡商店好像得变成女的吧…你怎么没有…还是说改进了？我现在飞车已卸载，改

8. 其实改车只是自慰，别人是看不见得。而且如果是真的的话你们看看凌哥改T2宝石是什么就知道了，还有用板车改T3速度能爆到几百？不过我还是很感谢凌哥的，为一些狗提供了骗钱的渠道。话说卡商店好像得变成女的吧…你怎么没有…还是说改进了？我现在飞车已卸载，改

9. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

10. 博主您好，这是一个内容十分优秀的博客，而且界面也非常漂亮。但是为什么博客的响应速度这么慢，虽然博客的主机在国外，但是我开启VPN还是经常响应很久，再者打开某些页面经常会出现数据库连接出错的提示