19.DFS-조합

https://leetcode.com/problems/combinations/

Combinations - LeetCode

 

 이번 포스팅에선 저번 순열에 이은 DFS로 조합에 대해 풀이해보겠다. 조합은 순열과 달리 원소의 순서가 달라도 구성되어져있는 원소의 종류가 같으면 같다고 처리해야한다. 예를들어 [1,3] 과 [3,1]은 조합에서 같은 것이다.

 

 순열에서 풀이했던 코드와 상당히 유사하다.

    def combine(n: int, k: int):
        sol=[]
        
        def dfs(index,array):
            if len(array) == k:
                sol.append(array)
                return
            
            for i in range(index,n):
                dfs(i+1,array+[nums[i]])

 다른점은 재귀적으로 호출되는 dfs의 index인자를 i+1로 주어야 하는점이다. 이뜻은 다음 dfs 함수에서 이전에 지나간 원소들은 확인할 필요가 없다는 의미이다.

 

 두번째 풀이는 itertools를 사용한 풀이이다. 이 풀이가 압도적으로 더 빠르다.

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