[LeetCode/Python] 77. 조합(Combinations)

전체 수 n을 입력받아 k개의 조합을 리턴하라.

 

Example:

 

Input: n = 4, k = 2

Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]

 

 

 

1. 내가 푼 코드

 

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        output = []
        nums = [i + 1 for i in range(n)]
 
        def dfs(k, stack=None):
            if stack is None:
                stack = []
            if k == 0:
                output.append(stack)
                return
            if stack:
                for w in nums[stack[-1]-1:]:
                    if w not in stack:
                        dfs(k-1,stack + [w])
            else:
                for w in nums:
                    if w not in stack:
                        dfs(k-1,stack + [w])
 
        dfs(k)
 
        return output
 

 

해설:

 

dfs를 이용하였다.

 

코드가 그때그때 추가한 거라 조잡한데 일단은...

 

k = 0이 되면 조합이 완성된 것이므로

 

output에 stack을 넣어준다.

 

그리고 16번 줄 처럼 원래 진행하려 했지만

 

순서가 바뀐 조합도 출력이 되어버려서

 

( [1,2]와 [2,1]처럼)

 

w보다 큰 것들만 조합하자!

 

라 생각하고 line12~15처럼 진행하였다.

 

 

 

 

** 깔끔한 답안 **

 

 

 

 

2. DFS로 k개 조합 생성

 

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
 

 

해설:

 

1번 코드에서는 nums를 따로 만들어 진행하였지만

 

이 코드는 nums를 만들지 않고 range를 이용하여 진행하였다.

 

 

 

 

 

 

3. itertools 모듈 사용

 

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

 

해설:

 

순열 문제에서 itertools 모듈을 사용했듯이

 

조합 문제에서도 사용할 수 있다.

 

이 경우 실행 속도는 제일 빠르다.