LeetCode 78. Subsets

파이썬 알고리즘 인터뷰 문제 37번(리트코드 78번) Subsets
https://leetcode.com/problems/subsets/

나의 풀이1(Iteration)

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

        for num in nums:
            for subset in result[:]:
                result.append(subset[:] + [num])
        
        return result
                

• 수학에서 수형도를 그리는 것을 생각해보면 된다.
• []과 여기에 1 추가한 [], [1]를 만들고,
• [], [1]과 여기에 2 추가한 [], [1], [2], [1, 2]를 만들고 ... 해나가면 된다.

나의 풀이2(Backtracking, 좋지 않음)

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

        def helper(index, path):
            if index == len(nums):
                result.append(path[:])
                return
            helper(index + 1, path)
            path.append(nums[index])
            helper(index + 1, path)
            path.pop()
            

        helper(0, [])
        return result

나의 풀이3(Backtracking)

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

        def helper(path, idx):
            result.append(path[:]) # 습관적으로 종료 조건을 idx == len(nums)로 해서 못풀었음.
            for i in range(idx, len(nums)):
                path.append(nums[i])
                helper(path, i + 1)
                path.pop()
        
        helper([], 0)
        
        return result

오답 및 배운 점

• 나의 풀이3에서 종료 조건을 잘못 생각해서 스스로 풀지 못했다. 복습이 필요함.