[LeetCode] 77. Combinations (그래프)

문제

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

Combinations - LeetCode

[1, n]의 범위를 가지는 숫자들에서 k개의 조합을 구하자.

 

내 풀이 1 (백트래킹)

 

순열과는 비슷하지만, 파라미터의 'start'를 for문에서 사용했다는 점이 다르다.

시간 : 712ms

 

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        n_list = [x for x in range(1, n+1)]
        check = [False]*n
        ans, temp = [], []
        def dfs(cnt, start):
            if cnt == k:
                ans.append(temp[:])
                return
            for i in range(start, n):
                if not check[i]:
                    check[i] = True
                    temp.append(n_list[i])
                    dfs(cnt+1, i)
                    check[i] = False
                    temp.pop()
                 
        dfs(0, 0)
        return ans

 

내 풀이 2 (combinations)

 

itertools가 요물이다.

시간 : 122ms

 

from itertools import combinations
class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        return list(combinations(range(1, n+1), k))

 

총평

코딩 테스트를 칠 때에는 파이썬 함수로 발라 놓으면 빨리, 그리고 효율적이게 풀 수 있을 것 같다.