90. Subsets II

O(n!) time

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(begin(nums), end(nums));
        n = nums.size();
        dfs(nums, 0);
        return res;
    }

    void dfs(const vector<int> &nums, int b) {
        res.push_back(v); // 每构造一个新结果就输出
        for (int i = b; i < n; ++i) {
            if (i > b && nums[i - 1] == nums[i]) continue; // 去重
            v.push_back(nums[i]);
            dfs(nums, i + 1);
            v.pop_back();
        }
    }

    int n;
    vector<int> v;
    vector<vector<int>> res;
};