Given a set of distinct integers, 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,3]
, a solution is:
[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
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], [] ]
思路:
排列组合题。对n个元素的集合S,一共有2^n个子集。其中每个元素都有“取”和“不取”两种状态。这样自然而然的就想到了用位操作解决。考虑到解长度的指数增长,不需要使用bitset之类的,直接用size_t已经足够了。
对于第二题,需要对每个相同元素的个数进行计数,然后递归即可。
题解:
class Solution { public: vector<vector<int> > subsets(vector<int> &S) { sort(begin(S), end(S)); // ensure non-descending results const size_t n = S.size(); const size_t num_sets = pow(2, n); vector<vector<int>> ret(num_sets); for(size_t bitwise = 0; bitwise < num_sets; ++bitwise) { size_t bit_chk = 1; for(size_t bit = 0; bit < n; ++bit) if ((bit_chk << bit) & bitwise) ret[bitwise].push_back(S[bit]); } return ret; } };
class Solution { public: vector<int> buffer; vector<vector<int>> result; vector<pair<int, int>> n_count; void build(vector<pair<int, int>>::iterator iter) { if (iter == end(n_count)) { result.push_back(buffer); return; } for(int i = 0; i <= iter->second; ++i) { build(next(iter)); buffer.push_back(iter->first); } for(int i = 0; i <= iter->second; ++i) buffer.pop_back(); } vector<vector<int> > subsetsWithDup(vector<int> &S) { result.clear(); if (S.empty()) return result; n_count.clear(); sort(begin(S), end(S)); int v = S.front(); int c = 0; for(auto& i : S) { if (v == i) ++c; else { n_count.push_back(make_pair(v, c)); v = i; c = 1; } } n_count.push_back(make_pair(v, c)); build(begin(n_count)); return result; } };