题目链接

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

题解

第一想法是按长度枚举，不过后来发现没办法列出所有情况，看了下官方题解才知道可以按照二进制枚举。

官方题解：

方法一：迭代法实现子集枚举

0/1 序列	子集	0/1 序列对应的二进制数
000	{}	0
001	{9}	1
010	{2}	2
011	{2,9}	3
100	{5}	4
101	{5,9}	5
110	{5,2}	6
111	{5,2,9}	7

复杂度分析：

• 时间复杂度： O(n \times 2^n)
  一共 2^n 个状态，每种状态需要 O(n) 的时间来构造子集。
• 空间复杂度： O(n)
  即构造子集使用的临时数组的空间代价。

迭代

class Solution {

    fun subsets(nums: IntArray): List<List<Int>> {
        val ans = mutableListOf<List<Int>>()
        val len = nums.size
        for (i in 0..1.shl(len)-1) { //0~2^n-1
            val list = mutableListOf<Int>()
            for (j in 0..len-1) {   //每一位
                if (i.and(1.shl(j)) != 0)   // &位运算，获取每一位不为0的数
                    list.add(nums[j])
            }
            ans.add(list)
        }
        return ans
    }
}

方法二：递归法实现子集枚举

复杂度分析

• 时间复杂度：O(n \times 2^n)
  一共 2^n 个状态，每种状态需要 O(n) 的时间来构造子集。
• 空间复杂度：O(n)
  临时数组的空间代价是O(n)，递归时栈空间的代价为O(n)。

递归

class Solution {

    val ans = mutableListOf<List<Int>>()
    val list = mutableListOf<Int>()
    fun subsets(nums: IntArray): List<List<Int>> {
        dfs(0,nums)
        return ans
    }

    fun dfs(cur:Int, nums: IntArray){
        if (cur==nums.size){
            val tmp = list.toList()
            ans.add(tmp)
            return
        }
        list.add(nums[cur])
        dfs(cur+1,nums)
        list.removeAt(list.size-1)
        dfs(cur+1,nums)
    }
}