[파이썬 알고리즘 인터뷰] 35. 조합

 

 이 포스팅은 파이썬 알고리즘 인터뷰를 공부하면서 정리한 내용입니다.

 

 출처 : 파이썬 알고리즘 인터뷰

 코드 출처 : 파이썬 알고리즘 인터뷰 깃허브

 

---

35. 조합

leetcode 77. Combiantion 문제입니다.

leetcode.com/problems/combinations/

 

 

풀이

1. 제가 푼 풀이

def combine(self, n, k):
    result = []
    
    def dfs(index, path):
        if len(path) == k:
            result.append(path)
            return

        for i in range(index, n+1):
            dfs(i+1, path + [i])

    dfs(1, [])
    return result

 

2. 책에 나와있는 풀이

def combine(n,k):
    results = []

    def dfs(elements, start, k):
        if k == 0:
            results.append(elements[:])

        for i in range(start, n+1):
            elements.append(i)
            dfs(elements, i+1, k-1)
            elements.pop()
    dfs([], 1, k)
    return results