[알고리즘] 조합

조합

책 풀이 1

def combine(n: int, k: int) -> List[List[int]]:
    result = []

    def dfs(elements, count, cur_num):
        if count == k:
            result.append(elements[:])
            return

        for i in range(cur_num, n+1):
            elements.append(i)
            dfs(elements, count + 1, i+1)
            elements.pop()

    dfs([], 0, 1)
    return result

[a,b,c,d]가 있으면 a를 넣고나서, b부터 또 보는 방시깅다. 여기서 중요한 점은 result.append(elements)라고 하면, dfs가 종료되고 elements.pop()이 있기 때문에 result에 있는 elements도 영향을 받을 수 있다는 점이다. 따라서 결과는 [:]로 연산자로 값 자체를 복사해 추가한다.

책 풀이2

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