[LeetCode] #77. Combinations (python)

문제

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

Combinations - LeetCode

주어진 정수 n, k를 가지고 [1, n] 범위로 가능한 k개의 조합을 반환해야 한다.

 

예시 입출력

Input: n = 4, k = 2
Output:
[
[2,4], [3,4], [2,3], [1,2], [1,3], [1,4],
]

 

 

풀이

 

책 풀이

1. dfs 활용

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

        def dfs(elements, start: int, k: int):
            if k == 0:
                results.append(elements[:])
                return

            # 자신 이전의 모든 값을 고정하여 재귀 호출
            for i in range(start, n + 1):
                elements.append(i)
                dfs(elements, i + 1, k - 1)
                elements.pop()

        dfs([], 1, k)
        return results

내가 풀려고 시도를 할 때 미리 범위에 해당하는 숫자 리스트를 만들었는데 책에서는 그냥 인덱스를 활용해 값을 추가했다. dfs 함수의 인자로 조합을 추가하는 변수 elements, 시작값, k를 넘겨준다.

시작값을 넘겨주기 때문에 자신을 제외한 값들이 잘 추가될 수 있다.

 

 

2. itertools 사용

import itertools

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return list(itertools.combinations(range(1, n + 1), k))

순열처럼 itertools 모듈을 사용해서 풀 수 있다. itertools.combinations()를 활용하면 된다.

 

 

참고한 책 : 파이썬 알고리즘 인터뷰