90.子集 II.md

90.子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

 

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

 

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

标签：

['位运算', '数组', '回溯']

难度：Medium

喜欢：917

---

DFS

算法思路

blablabla

复杂度分析

时间复杂度：$O(2^n)$

空间复杂度：$O(n)$

代码实现

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

    void dfs(int i){
        if (i == n){
            ans.push_back(path);
            return;
        }
        path.push_back(nums[i]);
        dfs(i+1);
        path.pop_back();
        while (i < n-1 && nums[i+1] == nums[i]) i++; // 去重；如果不选，后面相同的元素也不选
        dfs(i + 1);
    }
};

参考文献