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]]:
        
        def combine(nums, k):
            res = []
            def generate(chosen):
                if len(chosen) == k:
                    res.append(chosen[:])
                    return

                start = nums.index(chosen[-1]) + 1 if chosen else 0
                for nxt in range(start, len(nums)):
                    chosen.append(nums[nxt])
                    generate(chosen)
                    chosen.pop()
                    
            generate([])
            return res
            
        ans = [[]]
        for i in range(1, len(nums) + 1):
            ans.extend(combine(nums, i))
            
        return ans

앞서 다룬 combinations 문제에서는 정해진 k에 대한 조합을 구했다면 이번 문제에서는 모든 조합을 구하는 문제이다. 그렇기 때문에 앞서 combinations의 코드를 활용한다면 빠르게 풀 수 있는 문제이다.