[리트코드(LeetCode)] 77번 Combinations

문제

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

Combinations - LeetCode

전체 수 n을 입력받아 k개의 조합을 반환하는 문제다.

예시

Example 1:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

 

Example 2:

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

풀이

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
	
        def dfs(elements, start, k):
            if k == 0:
                res.append(elements[:])
                return
	# start : 현재 조합에 추가될 수 있는 숫자의 범위를 제한하여 중복된 조합 방지
            for i in range(start, n + 1):
                elements.append(i)
                dfs(elements, i + 1, k - 1)
                elements.pop()

        dfs([], 1, k)

        return res

 

- 깊이 우선 탐색(DFS)을 사용하여 크기가 k인 모든 조합을 생성한다.

- dfs 함수에서 'elements'는 현재까지 선택한 조합의 요소들을 나타내고 k가 0이 되면 요소들을 결과 리스트에 추가한다.

- start는 현재 조합에 추가될 수 있는 숫자의 범위를 제한하여 중복된 조합을 방지한다. 현재 위치(start)부터 n까지의 숫자를 확인하고 k개의 요소를 선택하고 재귀 호출한다.

 

참조 : 박상길, 파이썬 알고리즘 인터뷰  https://github.com/onlybooks/algorithm-interview