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을 활용하였다.