Leetcode - 78. Subsets
문제
Loading...
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
풀이
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
의외로 필요없는 부분이 많았다.