078._Subsets.md

78. Subsets

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/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],
  []
]

解题方案

思路 1

每次拿一个，跟res里面的每一个已有列表取并集再次插入res中

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = [[]]
        for num in nums:
            res.extend([tmp+[num] for tmp in res])
        return res     

思路 2

BackTrack 标准解法版

对每个元素，有两种可能，加入 cur_lst 和不加入 cur_lst，写起来思路还是很清爽的

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        
        def search(cur_lst, idx):
            if idx == len(nums):
                res.append(cur_lst)
                return
            search(cur_lst + [nums[idx]], idx + 1)
            search(cur_lst, idx + 1)
        
        search([], 0)
        return res

思路 3

DFS

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        def dfs(depth, start, lst):
            res.append(lst)
            if depth == len(nums):
                return
            for i in range(start, len(nums)):
                dfs(depth+1, i+1, lst+[nums[i]])
        dfs(0, 0, [])
        return res