ch12-4(leetcode 76). 조합

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 77번 ( https://leetcode.com/problems/combinations/ )

 

방법 1. 

itertools 모듈을 이용한다. 

 

itertools.combinations(n, k)

해당 모듈의 메소드는 총 n개의 원소 중 k개를 뽑는 조합의 경우의 수를 리스트로 리턴해 준다. 

def combine(self, n, k):
    return itertools.combinations(range(1, n+1), k)

 

방법 2. 

이전에 풀었던 순열 문제와 같은 방법으로, 내부 함수 dfs()를 선언한다. 

dfs(elements, k)에서는 elements에 포함된 n개의 원소 중 k개를 하나씩 뽑는다. 

뽑은 원소는 추가된 원소이므로 prev_elements에 추가하고, 다음에 탐색할 원소에서는 제외되므로 next_elements에서는 제외시킨다. 

 

시간 초과로 성공하지는 못했지만 정답을 리턴한다. 전체 코드는 다음과 같다. 

def combine(self, n, k):
        result = set()
        prev_elements = []

        def dfs(elements, k):
            if len(elements) == 0 or k == 0:
                contains = False
                for r in result:
                    a = set(tuple(prev_elements[:]))
                    b = set(r)
                    if len(a.difference(b)) == 0:
                        contains = True
                        break
                if not contains:
                    result.add(tuple(prev_elements[:]))
                return

            next_elements = elements[:]
            for e in elements:
                prev_elements.append(e)
                next_elements.remove(e)
                dfs(next_elements, k-1)
                prev_elements.remove(e)
                next_elements.append(e)

        dfs(range(1, n+1), k)
        return result

 

방법 3. (교재 참고)

순열과 달리 조합은 순서를 생각하지 않는다. 

그러므로 앞에서부터(1부터) 원소를 하나씩 추가해 왔다면 다음에 추가할 원소는 지금 있는 원소들보다는 뒤에 위치해 있다고 볼 수 있다. 

그러므로 dfs()의 매개변수로 몇 번째 인덱스를 기준으로 새로운 dfs()를 시작할지를 추가로 입력해 준다. 

 dfs(원소_리스트(elements), 다음_탐색_기준점(start), 남은_개수(k))

 

그러면 k개의 원소들을 모두 추가했을 때(k=0일 때) 추가로 results 변수에 있는 원소와 중복되는 것이 없는지 확인을 하지 않아도 된다. 

 

 

참고한 포스트

https://docs.python.org/3/tutorial/datastructures.html

https://docs.python.org/3/library/itertools.html#itertools.combinations

https://docs.python.org/3/library/copy.html