leetcode做题笔记|leetcode: II|leetcode|Subsets

Given a collection of integers that might contain duplicates, S, return all possible subsets.
【leetcode做题笔记|leetcode:】 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], [] ]

题目地址： https://oj.leetcode.com/problems/subsets-ii/ 解题思路：
与Subsets那道题相比，这道题的不同之处是给的数里面可能会有重复的。这样如果按照之前的解法，结果集中可能会出现相同的集合了。
Subsets那道题的解法是，每添加一个元素，该层集合=上一层的集合+上一层的每一个集合后面加上新添加的元素。
可以通过改成：每添加一个元素（如果是重复的），该层集合=上一层新添加的集合+上一层的每一个集合后面加上新添加的元素。
代码：

class Solution { public: vector > subsetsWithDup(vector &S) { vector > ret(1); sort(S.begin(),S.end()); int num=0; for(int i=0; i=1&&S[i]==S[i-1]) j=len-num; num=0; for(; j tmp=ret[j]; tmp.push_back(S[i]); ret.push_back(tmp); num++; } }return ret; } };