78. Subsets

描述

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解法

使用库函数。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        for i in range(len(nums) + 1):
            for tmp in itertools.combinations(nums, i):
                res.append(tmp)
        return res

每次遍历都把之前的结果加上新的元素再与之前的结果相加。例如 [1, 2, 3]：

第 1 轮：[[]] -> [[], [1]] 第 2 轮：[[], [1]] -> [[], [1], [2], [1, 2]] 第 3 轮：[[], [1], [2], [1, 2]] -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

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

递归（回溯）

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)

        def helper(i, tmp):
            res.append(tmp)
            for j in range(i, n):
                helper(j + 1, tmp + [nums[j]])

        helper(0, [])
        return res

参考

回溯算法