Leetcode No.90 子集 II（DFS）

一、题目描述

给你一个整数数组 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

二、解题思路

本题解基于No.78 子集，请读者在充分理解该题解后继续阅读。

考虑数组 [1,2,2][1,2,2]，选择前两个数，或者第一、三个数，都会得到相同的子集。

也就是说，对于当前选择的数 x，若前面有与其相同的数 y，且没有选择 y，此时包含 x 的子集，必然会出现在包含 y 的所有子集中。

我们可以通过判断这种情况，来避免生成重复的子集。代码实现时，可以先将数组排序；递归时，若发现没有选择上一个数，且当前数字与上一个数相同，则可以跳过当前生成的子集。

三、代码

class Solution {
public:
    vector<int> vec;
    vector<vector<int>> rs;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        dfs(false,0,nums);
        return rs;
    }
    void dfs(bool choosePre,int index,vector<int>& nums){
        if(index>=nums.size()){
            rs.push_back(vec);
            return;
        }
        dfs(false,index+1,nums);
        if(!choosePre && index>0 && nums[index]==nums[index-1]){
            return;
        }
        vec.push_back(nums[index]);
        dfs(true,index+1,nums);
        vec.pop_back();
        
    }
};

四、复杂度分析

时间复杂度：O(n×2^n)，其中 n 是数组 nums 的长度。排序的时间复杂度为 O(nlogn)。最坏情况下 nums 中无重复元素，需要枚举其所有 2^n个子集，每个子集加入答案时需要拷贝一份，耗时 O(n)，一共需要 O(n×2^n)+O(n)=O(n×2^n) 的时间来构造子集。由于在渐进意义上 O(nlogn) 小于 O(n×2^n)，故总的时间复杂度为 O(n×2^n)。

空间复杂度：O(n)。临时数组 t 的空间代价是 O(n)，递归时栈空间的代价为O(n)。