Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]解题思路：与78题不同，本题可能存在相同的元素，如何删除相同的集合则是本题的难点。
以[1,2,2]为例，以78解题思路（回溯剪枝），得到子集的顺序为[[],[1],[1,2],[1,2,2],[1,2],[2],[2,2],[2]]，相当于先找到第一个元素构成的所有子集，再找第二个元素构成的子集，由此类推，如果继续采用这种思路，在剔除的时候会有点麻烦。
本题用另外一种思路，与78题中的非递归解法一致，从最终结果来看，求得子集顺序为[[],[1],[2],[1,2],[2],[1,2],[2,2],[1,2,2]]，即先求元素个数为0的子集，接着求个数为1的子集，由此类推，具体做法如下：
先将nums排序，来保证所有相同的元素在一起，设一个ans数组记录已经有的子集，将空集压入。
压入1：调出空集，将1压入得到[[],[1]]
压入2：首先调出[]，得到[2]，再调出[1]，得到[1,2]，当前结果为[[],[1],[2],[1,2]]。
压入第二个2：从第二次得出的子集，依次再在每个子集中压入2，最终得到[[],[1],[2],[1,2],[2],[1,2],[2,2],[1,2,2]]
此即为78题非递归的解法，如果要用于本题，在压入第二个2的时候，需要去除[[],[1],[2],[1,2]]中不含有第一个2的子集，在剩下的子集中压入第二个2。换言之，需要修改left。
当此时num的值与上一次遍历的值一致，left应该为压入上一个num值前的子集个数。
class Solution { public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>>ans; vector<int>tempans; ans.push_back(tempans); int right = 1, left = 0, len = 0; for(int i = 0; i < nums.size(); ++ i){ if(i != 0 && (nums[i] == nums[i-1])) left = ans.size() - len; else left = 0; right = ans.size(); len = right - left; for(int j = left; j < right; ++ j){ tempans = ans[j]; tempans.push_back(nums[i]); ans.push_back(tempans); } } return ans; } };
