分析

• 本题的考点：递归回溯。

• Leetcode 0078 子集中可以使用位运算，是因为数组中的元素都不相同。这一题不能使用位运算，因为存在重复元素。

• 首先对数组进行排序，这样方便处理重复元素，对于出现多次的元素，在暴搜过程中直接过滤掉即可。

• 这一题的做法和Leetcode 0040 组合总和II的做法十分类似。

代码

• C++

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;

    vector<vector<int>> subsetsWithDup(vector<int> &nums) {

        sort(nums.begin(), nums.end());
        dfs(nums, 0);
        return res;
    }

    // u: 当前考察的是nums[u]
    void dfs(vector<int> &nums, int u) {

        if (u == nums.size()) {
            res.push_back(path);
            return;
        }

        int k = u + 1;
        while (k < nums.size() && nums[k] == nums[u]) k++;

        for (int i = 0; i <= k - u; i++) {
            dfs(nums, k);
            path.push_back(nums[u]);
        }

        for (int i = 0; i <= k - u; i++) path.pop_back();
    }
};

• Java

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        Arrays.sort(nums);
        dfs(nums, 0);
        return res;
    }

    private void dfs(int[] nums, int u) {

        if (u == nums.length) {
            res.add(new LinkedList<>(path));
            return;
        }

        int k = u + 1;
        while (k < nums.length && nums[k] == nums[u]) k++;

        for (int i = 0; i <= k - u; i++) {
            dfs(nums, k);
            path.add(nums[u]);
        }

        for (int i = 0; i <= k - u; i++) path.removeLast();
    }
}

时空复杂度分析

• 时间复杂度：$O(2^n)$，n为数组长度。

• 空间复杂度：考虑结果的存储 $O(2^n)$。