[LeetCode][Python3] 77. Combinations

Problem :

https://leetcode.com/problems/combinations/

My Solution :

class Solution:

def combine(self, n, k):

def comb(n, k):

if (n, k) in memo:

return memo[(n, k)]

if n < k:

return []

if k == 1:

memo[(n, k)] = [[x] for x in range(1, n+1)]

return memo[(n, k)]

part1 = comb(n-1, k-1)

part2 = comb(n-1, k)

res = []

for part in part1:

res.append(part + [n])

res.extend(part2)

memo[(n, k)] = res

return memo[(n, k)]

memo = dict()

return comb(n, k)

Comment :

nCr = n-1Cr-1 + n-1Cr 임을 활용하였으며, 중복 계산을 피하기 위해 memoization을 활용하였다.