Python 알고리즘 인터뷰 - 문제 35. 조합

leetcode 39. Permutations - https://leetcode.com/problems/combinations/submissions/1174708118/

 

문제

입력 : n = 4, k = 2

 

출력

[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

 

풀이 

조합은 n개의 숫자 리스트 중 K개의 중복되지 않은 숫자 조합을 뜻한다. 이를 위해 n=5, k=3을 예로 들어 설명하면 다음과 같다.

 

다음과 같이 i는 1~n까지 순회하며, k는 -1이 계속 진행하여, 0이 될 때까지 순회을 진행한다.

조합은 이전의 방문한 문자를 포함하면 안되기 때문에 함수 호출에서 포함된 문자보다 1이 증가된 방향으로 진행한다.

 

k=1인 경우는 leaf node이다. 이후 함수호출 시 k=0인 경우에 조합된 숫자를 리스트에 추가한다.이후 i=3~5 까지 순차적으로 결과 리스트에 값을 저장한다.

i가 n까지 도착되면 k=1에서의 순회는 완료되고 k=2, i=3에서부터 조합을 다시 생성한다.

이를 코드로 나타내면 다음과 같다.

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

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

 

여기서 주의할 점은 elements는 리스트이므로 파라미터에 '참조'로 전달된다. 각 함수 호출에서 elements는 동일한 메모리를 가리키므로  append가 될 경우 모든 재귀함수 호출에서 동일하게 값이 변경된다. 따라서 dfs가 반환될 때 elements를 pop하고 results에 추가할 때는 elements[:]를 전달하여 값을 복사한다.

 

전체코드는 다음과 같다.

def combine(n, k):
    if n == 0:
        return []

    results = []

    def dfs(elements, start, k):
        if k == 0:
            results.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 results