算法题--寻找数组的所有子集

image.png

0. 链接

题目链接

1. 题目

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],
  []
]

2. 思路1：回溯法

• 每个子集的元素数可以为[0, len(nums)]
• 对于每个元素数, 就是一个组合选取问题
• 组合选取问题采用回溯法, 在回溯的每一步:
  • 选择范围: [start, len(nums) - 1]
  • 选择元素
  • 更新start和k
  • 撤销选择
  • 当k=0时, 代表捕获了一个合法子集

3. 代码

# coding:utf8
from typing import List


class Solution:
    def combine(self, combs: List[List[int]], comb: List[int], nums: List[int], start: int, k: int):
        if k == 0:
            combs.append(comb.copy())
        else:
            for i in range(start, len(nums)):
                comb.append(nums[i])
                self.combine(combs, comb, nums, i + 1, k - 1)
                comb.pop()

    def subsets(self, nums: List[int]) -> List[List[int]]:
        combs = list()
        comb = list()
        for i in range(len(nums) + 1):
            self.combine(combs, comb, nums, 0, i)
        return combs


def my_test(solution, nums):
    print('input={}, output={}'.format(nums, solution.subsets(nums)))


solution = Solution()
my_test(solution, [1, 3, 5])

输出结果

input=[1, 3, 5], output=[[], [1], [3], [5], [1, 3], [1, 5], [3, 5], [1, 3, 5]]

4. 结果

image.png