题意整理

• 有一个没有重复元素的整数集合S，求S的所有子集。
• 要求子集升序排列，并且没有重复子集。

方法一（mask枚举）

1.解题思路

• 对S排序。
• 利用子集对应的二进制编码mask枚举所有的子集。
• mask总共有n位，0表示不选取当前下标对应的字符，1表示选取当前下标对应的字符。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    //记录所有子集
    ArrayList<ArrayList<Integer>> res=new ArrayList<>();
    //记录当前子集
    ArrayList<Integer> list=new ArrayList<>();
    
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        //对S排序
        Arrays.sort(S);
        int n=S.length;
        //遍历所有mask，每一个mask表示一个子集的二进制编码，0表示不选当前字符，1表示选
        for(int mask=0;mask<(1<<n);mask++){
            //清空list
            list.clear();
            for(int i=0;i<n;i++){
                //将mask转化为对应的子集
                if((mask&(1<<i))!=0){
                    list.add(S[i]);
                }
            }
            //添加转化完成的子集
            res.add(new ArrayList<>(list));
        }
        return res;
    }
    
}

3.复杂度分析

• 时间复杂度：排序的时间复杂度为$O(nlo{g}_{2}n)O(nlog\_2n)$，另外枚举mask时，每一位可选可不选，有n位，从而有$2^{n}2^n$个mask，每个mask转化为子集需要$O(n)O(n)$的时间复杂度，所以时间复杂度为$O(n\ast 2^n)O(n*2^\{n\})$
• 空间复杂度：需要额外大小为n的临时list存储子集，所以空间复杂度是$O(n)O(n)$。

方法二（递归）

1.解题思路

• 递归终止条件：构造完当前子集。
• 递归如何推进：确定好当前字符是否添加之后，直接从下一个字符开始继续进行添加。

2.代码实现

import java.util.*;

public class Solution {
    //记录所有子集
    ArrayList<ArrayList<Integer>> res=new ArrayList<>();
    //记录当前子集
    ArrayList<Integer> list=new ArrayList<>();
    
    public ArrayList<ArrayList<Integer>> subsets(int[] S) {
        //排序
        Arrays.sort(S);
        //递归遍历所有情况
        dfs(0,S);
        return res;
    }
    
    private void dfs(int index,int[] S){
        //添加当前子集
        res.add(new ArrayList<>(list));
        for(int i=index;i<S.length;i++){
            //添加当前字符
            list.add(S[i]);
            //从下一位递归
            dfs(i+1,S);
            list.remove(list.size()-1);
        }
    }
}

3.复杂度分析

• 时间复杂度：一共有$2^{n}2^\{n\}$种状态，每种状态需要$O(n)O(n)$的时间来构造，所以时间复杂度为$O(n\ast 2^n)O(n*2^\{n\})$
• 空间复杂度：需要额外大小为n的临时list存储子集，所以空间复杂度是$O(n)O(n)$。