프로그래밍/LeetCode
[LeetCode][Python3] 77. Combinations
snoopybox
2019. 8. 25. 00:45
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을 활용하였다.