[리트코드] Combinations(python)

리트코드, Combinations_조합

TL;DR

• 깊이 우선 탐색(DFS)

문제 분석

[1, n] 범위의 수로 만들 수 있는 k개의 모든 가능한 조합을 반환하라.

 

- 1 ~ n 사이의 수에 대해서 k개를 뽑아 만들 수 있는 모든 조합을 반환하면 된다.

입출력 형태

입출력 예시

 

- 1 ~ 4 사이의 숫자에서 2개를 뽑아 만들 수 있는 모든 조합을 반환하고 있다.

- 만들 수 있는 조합의 개수는 공식(`n! / (n - k)!k!`)에 따라 6개가 반환되어야 한다. 

틀린 풀이

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:      
        answer = []
        
        def dfs(vertex: int, combinations: List[List[int]] = []):
            combinations.append(vertex)
            
            if len(combinations) == k:
                if sorted(combinations) not in answer:
                    answer.append(combinations)
                return
            
            for i in range(1, n + 1):
                if i not in combinations:
                    dfs(i, combinations[:])
                    
        for i in range(1, n + 1):
            dfs(i, [])
        
        return answer

 

이전에 푼 순열 문제와 유사한 방법으로 해결하려고 했다. 단, 조합은 중복된 경우를 포함시키지 않으므로 생성한 조합을 정렬하여 조합을 담는 배열에 있는지 확인한 후 정답에 포함시키는 방식으로 문제를 풀었다.

단, 이 방식의 경우 n과 k가 커짐에 따라 시간 초과 문제가 발생한다. 이미 만든 조합은 다시 만들어서 확인하지 않도록 하는 방법이 필요하다.

풀이

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:      
        answer = []
        
        def dfs(elements: List[int], start: int, k: int):
            if k == 0:
                answer.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 answer

 

올바르게 된 풀이 방법이다.

DFS를 재귀적으로 구현한 함수는 조합들을 저장할 elements과 시작 인덱스인 start, 그리고 조합의 개수를 나타내는 k로 구성되어 있다.

시작 인덱스를 증가시키고, 조합의 개수를 감소시키며 반복한다. 더 이상 조합의 개수를 만들 수 없다면 종료한다.

이 과정을 통해 조합을 구할 수 있다.

단, 이 방법 또한 시간이 매우 많이 드는 방법이다. 알고리즘을 공부하는 느낌은 아니지만 시간 복잡도를 가장 줄이는 방법이 있다.

또 다른 풀이

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

 

바로 `itertools` 모듈을 사용하는 것이다. 이 방법을 통해 한 줄로 보다 빠르게 조합을 구할 수 있다.

단, 이 때 튜플의 형식으로 정답이 반환되므로 문제에서 원하는 출력 형태인 리스트로 형 변환을 해줘야 한다.