LeetCode - 77. Combinations [Python]

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

Combinations - LeetCode

---

풀이 과정

주어진 n개의 원소의 리스트에서 k개의 숫자로 이루어진 조합을 구하는 문제이다.

 

https://greentea31.tistory.com/111?category=939228 

재귀로 조합 구현하기 [C++}

 

위의 글의 코드를 구현하였다. 1~4까지의 수를 원소로 가진 리스트에서 2개를 뽑아 조합을 만들어야 한다면 1을 고르는 것과 안고르는 것, 2를 고르는 것과 안고르는 것, 3을 고르는 것과 안고르는 것, 4를 고르는 것과 안고르는 것... 이런식으로 구하다 골라야 하는 수가 4를 넘어가거나, 이미 고른 수가 2를 넘어가면 그만두게 하고, 이미 고른 수가 2개가 되는 경우마다 정답 배열에 추가해 주면 모든 조합을 구할 수 있다.

 

책에서 본 좋은 코드도 재귀 2에 기록해 두었고, itertools 모듈의 combinations 함수를 사용하면 문제를 더 쉽게 해결할 수 있다.

 

---

소스 코드

재귀 1

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        answer = []
        output = [-1 for _ in range(k)]
        
        def combination(index, selected):
            if selected == k:
                answer.append(output[:])
                return
            if index > n:
                return
            
            output[selected] = index
            combination(index+1, selected+1)
            combination(index+1, selected)
        
        combination(1, 0)
        return answer

 

재귀 2

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        results = []
        
        def combination(elements, start, k):  # 추가된 원소, 탐색 시작점, 넣어야 될 남은 원소 개수
            if k == 0:  # 다 넣었으면 정답 추가
                results.append(elements[:])
                return
            
            for i in range(start, n+1):
                elements.append(i)  # i를 넣는 경우
                combination(elements, i+1, k-1)
                elements.pop()  # i를 넣지 않는 경우
        
        combination([], 1, k)
        return results

 

itertools

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