一道题，三种解，其中两种实现了，但是代码都不够简洁，记录了简洁版本的代码以供参考。

题目

给定一组不含重复元素、也不一定连续的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

示例

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

考察知识点

位运算、数组、回溯算法

核心思想

方法一、回溯

复杂回溯

设置子集长度 k 从 0 开始一直到 len(nums)
每次都调用 combine 输入nums、nums的长度n、需要的组合的长度 k，得到 nums 长度为 k的子集的集合。将结果累加到同一个 list 即为最终答案。先循环，然后在循环里面回溯。

res = []
nums.sort()
n = len(nums)
for i in range(len(n+1)):
	res += self.combine(nums, n, k)

简答回溯

实际上，这么写代码，虽然可以实现功能，但是把问题复杂化了。既然求的是幂子集，那直接去掉终止条件不就行了吗？

方法二、一次遍历（递归）
这个题蛮有意思的，可以直接从后遍历，遇到一个数就把所有子集加上该数组成新的子集，遍历完毕即是所有子集。

方法三、状态分配（字典排序（二进制排序） 子集）

把数组中所有的数分配一个状态，true 表示这个数在子集中出现，false 表示在子集中不出现，那么对于一个长度为 \(n\) 的数组，每个数字都有出现与不出现两种情况，所以共有 \(2n\) 中情况，那么我们把每种情况都转换出来就是子集了，我们还是用题目中的例子, [1 2 3] 这个数组共有8个子集，每个子集的序号的二进制表示，把是1的位对应原数组中的数字取出来就是一个子集，八种情况都取出来就是所有的子集了。

	1	2	3	Subset
0	F	F	F	[]
1	F	F	T	3
2	F	T	F	2
3	F	T	T	23
4	T	F	F	1
5	T	F	T	13
6	T	T	F	12
7	T	T	T	123

上表的状态存储用位运算来实现

Python版本

• 方法一的实现

复杂回溯

class Solution:
    def combine(self, nums, n, k):
        def backtrack(start = 0, path = []):
            cur_len = len(path)
            if cur_len == k:
                res.append(path[:])
                return 
            for i in range(start, n - (k - cur_len) + 1):
                d = nums[i]
                path.append(d)
                backtrack(i + 1, path)
                path.pop()

        if k == n:  return [nums]
        if n <= 0 or k <= 0 or k > n:  return [[]]
        res = []
        backtrack()
        return res
    
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()
        n = len(nums)
        for k in range(0, n+1):
            res += self.combine(nums, n, k)
        return res


Input = [[3,9], [1,2,3]]
Answer = [
    [[],[3],[9],[3,9]],
    [[3], [1], [2], [1,2,3], [1,3], [2,3], [1,2],[]]
]

if __name__ == "__main__":
    solution = Solution()
    for i in range(len(Input)):
        print("-"*50)
        reslut = solution.subsets(Input[i])
        if reslut == Answer[i]:
            print(True)
        else:
            print(False)
            print(reslut)
            print(Answer[i])

时间复杂度：\(O(N \times 2^N)\)，生成所有子集，并复制到输出集合中。
空间复杂度：\(O(N \times 2^N)\)，存储所有子集，共 \(n\) 个元素，每个元素都有可能存在或者不存在。
行用时 :56 ms, 在所有 Python3 提交中击败了14.36%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了5.46%的用户

复杂回溯的另一种写法

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(first = 0, curr = []):
            if len(curr) == k:  
                output.append(curr[:])
                return
            for i in range(first, n - (k - len(curr)) + 1):
                curr.append(nums[i])
                backtrack(i + 1, curr)
                curr.pop()
        
        output = []
        n = len(nums)
        for k in range(n + 1):
            backtrack()
        return output

执行用时 :36 ms, 在所有 Python3 提交中击败了76.86%的用户
内存消耗 :13.7 MB, 在所有 Python3 提交中击败了5.46%的用户

简单回溯

class Solution:
    def subsets(self,nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return []
        n = len(nums)
        res = []
        nums.sort()

        def backtrack(idx, n, temp_list):
            res.append(temp_list)
            for i in range(idx, n):
                helper1(i + 1, n, temp_list + [nums[i]])

        backtrack(0, n, [])
        return res

• 方法二 一次遍历（递归）

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]: 
        res = [[]]
        for i in nums:
            tmp_res = res[:]
            for j in res:
                new = j[:]
                new += [i]
                tmp_res += [new[:]]
            res = tmp_res[:]
        return res

时间复杂度：\(O(N \times 2^N)\) ，生成所有子集，并复制到输出结果中。
空间复杂度：\(O(N \times 2^N)\) ，这是子集的数量。
对于给定的任意元素，它在子集中有两种情况，存在或者不存在（对应二进制中的 0 和 1）。因此，\(N\) 个数字共有 \(2^N\) 个子集。
执行用时 :40 ms, 在所有 Python3 提交中击败了53.70%的用户
内存消耗 :13.7 MB, 在所有 Python3 提交中击败了5.46%的用户

一次遍历的另一种简洁写法

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        output = [[]]
        for num in nums:
            output += [curr + [num] for curr in output]
        return output

执行用时 :40 ms, 在所有 Python3 提交中击败了53.70%的用户
内存消耗 :13.7 MB, 在所有 Python3 提交中击败了5.46%的用户

• 方法五 状态分配

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def convertIntToSet(nums, k):
            sub = []
            idx = 0
            i = k
            while i>0:
                if i & 1 == 1:
                    sub.append(nums[idx])
                idx += 1
                i >>= 1
            return sub
        res = []
        nums.sort()
        _max = 1 << len(nums)
        k = 0
        while k < _max:
            out = convertIntToSet(nums, k)
            res.append(out)
            k += 1
        return res

执行用时 :60 ms, 在所有 Python3 提交中击败了9.75%的用户
内存消耗 :13.6 MB, 在所有 Python3 提交中击败了5.46%的用户

参考链接

LeetCode
Grandyang