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.
For example,
If nums = [1,2,2], a solution is:
[ [2], [1], [1,2,2], [2,2], [1,2], [] ]
使用回溯法求解，要求结果不能包含重复的子集。
所以先对给定数组排序后利用find函数去重。
class Solution { public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { vector<vector<int>> res; vector<int> tmp; int idx = 0; sort(nums.begin(), nums.end()); helper(res, tmp, nums, idx); return res; } void helper(vector<vector<int>>& res, vector<int>& tmp, vector<int>& nums, int idx) { if (find(res.begin(), res.end(), tmp) == res.end()) res.push_back(tmp); for (int i = idx; i < nums.size(); i++) { tmp.push_back(nums[i]); helper(res, tmp, nums, i + 1); tmp.pop_back(); } } }; // 12 ms