[파이썬 알고리즘] 12장 - 조합 (leetcode 77) ⭐

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

Combinations - LeetCode

<문제>

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

You may return the answer in any order.

 

<풀이>

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


Input: n = 1, k = 1
Output: [[1]]

---

1. DFS를 이용한 풀이

class Solution2:
    def combine(self, n: int, k: int) -> List[List[int]]:
    	# remainder 개념을 사용한 이유는 빈 리스트가 입력으로 들어왔을 때도 동일하게 동작하기 위함
        def dfs(level: int, partial_list: List, remainder: int):
            if len(partial_list) == k:
                answer.append(partial_list)
                return
            for i in range(remainder, n-k+level+1):
                dfs(level+1, partial_list + [i], i+1)

        answer = []
        dfs(1, [], 1)
        return answer

 

 

 

 

level이라는 개념을 사용한 이유는 각 층마다 최대값이 제약되기 때문이다.

(오름차순 순서로 요소를 추가해나갈 계획이기 때문이다)

 

N=5, K=3일 때

level1, 즉 첫 번째 요소의 최댓값은 3이다. 

level2, 즉 두 번째 요소의 최댓값은 4이다.

level3, 즉 마지막 요소의 최댓값은 5이다.

 

이처럼 level에 따라 최댓값이 달라지기 때문에 dfs의 인자로 level을 넣어준 것이다.

 

dfs(1, [], 1)을 호출하면 dfs(2, [1], 2), dfs(2, [2], 3), dfs(2, [3], 4)를 호출하게 된다.

그리고 dfs(2, [1], 2)는 dfs(3, [1, 2], 3), dfs(3, [1, 3], 4), dfs(3, [1, 4], 5)를 호출하게 된다.

이런식으로 재귀적으로 호출하게 되고,

 

재귀함수의 종료조건은 partial list의 원소의 개수와 K가 동일한 경우이다.

이 경우 answer에 partial_list를 append한 뒤 return하게 된다.

 

---

2. itertools.combinations 이용한 풀이

# faster than 96% (76ms)
# less than 52% (15.7MB)
class Solution3:
    def combine(self, n: int, k: int):
        import itertools
        return list(itertools.combinations(range(1, n+1), k))

 

코딩테스트에서는 다음과 같은 풀이를 사용할 수 있겠지만,

면접에서는 위와 같은 풀이를 메인 풀이로 사용하지 않기를 추천한다.

(부가적으로 이러이러한 기능이 있다고 언급해주는 정도로만 ...)