Combinations
문제 파악
주어진 범위 내에서 숫자를 조합하여 주어진 길이의 조합을 찾는 문제
접근 방법
백트래킹을 통해 재귀적으로 조합을 찾기
curr
의 길이가 주어진 길이k
와 같아지면, 해당 조합을 결과 리스트에 추가후 종료- 그렇지 않다면,
start
부터n
까지의 숫자를 손회하면서 현재 조합에 해당 숫자가 없으면 추가후, 재귀적으로 다음 숫자를 탐색 - 재귀 호출이 끝나면 해당 숫자들을 제거
코드 구현
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def backtrack(start, curr):
# base case
if len(curr) == k:
ans.append(curr[:])
return
for num in range(start, n + 1):
if num not in curr:
curr.append(num)
backtrack(num + 1, curr)
curr.pop()
ans = []
backtrack(1, [])
return ans
배우게 된 점
새로운 점을 배웠다면, 백트래킹을 응용해서 문제 해결 방법을 익혔다. 이러한 방식은 순열, 조합 뿐만 아니라 다양한 조합관련 문제를 해결하는데 유용.
Leave a comment