[알고리즘][그래프] - 4. 조합

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님' 책을 보고 작성되었습니다.

---

😎문제 : https://leetcode.com/problems/combinations/

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

---

[DFS로 k개 조합 생성]

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

[itertools 모듈 사용]

import itertools

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