LeetCode 77(Combinations, Python)

1. 문제 링크

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

Combinations - LeetCode

2. 문제 설명

• 주어진 자연수 n과 k에 대해, 1부터 n까지의 숫자 중에서 중복과 순서 없이 k개 고르는 조합을 모두 반환
• 예시) n=4, k=2이면 [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]를 반환

3. 처음 풀이

• 백트래킹 이용

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []

        def travel(path, n, k):
            # 현재 경로의 길이가 목표 길이와 같다면 결과에 추가
            if len(path) == k:
                result.append(path[:])
                return

            # 현재 경로가 비어있으면 시작점을 0으로, 아니면 마지막 요소를 시작점으로 설정
            if len(path) == 0:
                path_max = 0
            else:
                path_max = path[-1]

            # 시작점부터 n까지의 숫자 중에서 하나씩 선택하여 재귀 호출
            for x in list(range(path_max+1, n+1)):
                path.append(x)
                travel(path, n, k)
                path.pop()

        # 초기 호출
        travel([], n, k)

        return result

4. 다른 풀이

• 조금 더 간결한 백트래킹

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []

        def backtrack(start, path):
            if len(path) == k:
                res.append(path[:])
                return
            for i in range(start, n + 1):
                path.append(i)
                backtrack(i + 1, path)
                path.pop()

        backtrack(1, [])
        return res

5. 배운 점

• 아직까지 backtracker를 자유자재로 쓰지 못해서 코드가 간결하지 못하다.
• 다른 사람들 코드를 좀 더 많이 보고 배워야 함.