题目主要信息

1、重复元素的整数集合S，求S的所有子集

2、子集中的元素必须按升序排列

3、给出的解集中不能出现重复的元素

方法一：回溯

看到这题就直接想到的就是回溯，把回溯的模板修改一下就行。

具体做法

由于题目要求子集中的元素需要升序排列，所以先对初试的数组进行排序，然后在使用回溯法求解。 举例如下num = [1,2,3]

Java代码

import java.util.*;

public class Solution {
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        ArrayList<Integer> temp = new ArrayList<>();
        //排序 
        Arrays.sort(S);
        dfs(S,result,temp,0);
        return result;
    }
    public void dfs(int []num,ArrayList<ArrayList<Integer>> result,ArrayList<Integer> temp,int start){
        //当前加入到result中
        result.add(new ArrayList<>(temp));
        for(int i = start;i<num.length;i++){
            //将当前值加入temp中
            temp.add(num[i]);
            dfs(num,result,temp,i+1);
            //回溯到上一层
            temp.remove(temp.size()-1);
        }
    }
}

复杂度分析

• 时间复杂度：$O(n\ast 2^n)O(n*2^n)$一共 $2^{n}2^n$个状态，每种状态需要 $O(n)O(n)$ 的时间来构造子集。
• 空间复杂度：$O(n)O(n)$。临时数组的空间代价是 $O(n)O(n)$

方法二：迭代法

具体做法

这个方法很巧妙，就是时间复杂度有点大，我们举例说明

记原序列中元素的总数为 n。原序列中的每个数字 num[i]的状态可能有两种，即在子集中和不在子集中。我们用 1 表示在子集中，0 表示不在子集中，那么每一个子集可以对应一个长度为 n 0/1 序列。num = [1,2,3]

可以发现 0/1 序列对应的二进制数正好从 0 到 $2^n-12^n-1$,可以进行枚举从0-$2^n-12^n-1$

Java代码

import java.util.*;

public class Solution {
    ArrayList<Integer> temp = new ArrayList<Integer>();
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

    public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); ++mask) {
            //清空
            temp.clear();
            boolean flag = true;
            for (int i = 0; i < n; ++i) {
                if ((mask & (1 << i)) != 0) {
                  //迭代时，若发现没有选择上一个数，且当前数字与上一个数相同，则可以跳过当前生成的子集。
                    if (i > 0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i - 1]) {
                        flag = false;
                        break;
                    }
                    temp.add(nums[i]);
                }
            }
            if (flag) {
                result.add(new ArrayList<Integer>(temp));
            }
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：$O(n\ast 2^n)O(n*2^n)$,共 $2^{n}2^n$个状态每种状态需要 $O(n)O(n)$ 的时间来构造子集。
• 空间复杂度：$O(n)O(n)$。即构造子集使用的临时数组 temp 的空间代价。