Leetcode - 78. Subsets

문제

풀이

class Solution:
    def subsets(self, nums):
        memo = [[] for _ in range(len(nums) + 1)]
        memo[-1] = [[nums[-1]]]
        for idx, num in enumerate(reversed(nums)):
            if idx == 0:
                continue
            subtree = [[]]
            for ii in range(idx + 1):
                if memo[len(nums) - ii]:
                    subtree.extend(memo[len(nums) - ii])

            memo[len(nums) - (idx + 1)] = [[num] + node for node in subtree]

        res = [[]]
        for mem in memo:
            res += mem
        return res

Dynamic programming으로 풀었다. nested list로 만드는 게 좀 맘에 안든다.

코드를 좀더 간결하게 고쳐보면,

class Solution:
    def subsets(self, nums):
        memo = [[]]
        for num in nums:
            memo += [[num] + node for node in memo]

        return memo

의외로 필요없는 부분이 많았다.