78_子集

类型：数组

• 78. 子集 💛

  https://leetcode-cn.com/problems/subsets/

  ❓ 给你一个整数数组 nums ，数组中的元素互不相同 。返回该数组所有可能的子集。

  💡 回溯法

  参见 回溯法

  class Solution:
      def subsets(self, nums: List[int]) -> List[List[int]]:
  
          n = len(nums)
          track = []
          ans = []
  
          def trackback(start):
              ans.append(track[:])
              for i in range(start, n):
                  track.append(nums[i])
                  trackback(i + 1)
                  track.pop()
  
          trackback(0)
          return ans

  时间复杂度：O(n * 2^n)，一共 2^n 种状态，每种状态需要 O(n) 的时间来构造子集。

  空间复杂度：O(n)