题目链接：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个整数集合（集合中可以包含重复元素），返回其所有子集。要求子集中的元素以非递减的顺序排列，且不包含重复子集。
这是Subsets的扩展，在其基础上使数组中允许重复元素。思路就是在处理Subsets的基础上加个跳过重复元素即可。
其中b为子集的起始位置，n为子集的元素数量。
时间复杂度：O(n*2^n)（结果数量）
空间复杂度：O(n*2^n)（结果数量）
1 class Solution
2 {
3 vector<vector<int> > vvi;
4 public:
5 vector<vector<int> > subsetsWithDup(vector<int> &S)
6 {
7 sort(S.begin(), S.end());
8 vector<int> vi;
9 vvi.push_back(vi);
10 for(int i = 1; i <= S.size(); ++i)
11 subsetsWithDup(S, vi, 0, i);
12 return vvi;
13 }
14 private:
15 // b为子集的起始位置，n为子集的元素数量
16 void subsetsWithDup(vector<int> &S, vector<int> vi, int b, int n)
17 {
18 if(n == 0)
19 vvi.push_back(vi);
20 else
21 for(int i = b; i < S.size() + 1 - n; )
22 {
23 vi.push_back(S[i]);
24 subsetsWithDup(S, vi, i + 1, n - 1);
25 vi.pop_back();
26 while(S[++i] == S[i - 1]); // 跳过重复元素
27 }
28 }
29 };