LeetCode 77번 Combinations

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

---

문제 파악

주어진 수를 통해 해당 수의 조합이 몇개가 가능할지 풀고 출력하는 문제.

접근 방법

조합은 순서가 없기 때문에 순열과 다르게 백트래킹을 통해 중복되는 부분을 필터링해서 풀자

코드 구현

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        def backtracking(start, curr):
            if len(curr) == k:
                result.append(curr[:])
                return
            
            for i in range(start, n+1):
                curr.append(i)
                backtracking(i+1, curr)
                curr.pop()
        
        backtracking(1, [])
        return result

순열처럼 백트래킹을 사용하지만 중복된 부분을 제거해줘야 하기 때문에 start부분을 사용해서 i+1부터 조합을 만들어 중복되는 부분을 없애준다.

배우게 된 점

백트래킹을 사용하는 방법과 이와 관련해 어떻게 답을 뽑아내고 어떻게 접근해야 하는지 생각하는 시간을 가지게 되어서 유익했다.