[Leetcode] - 77

• 조합/순열은 itertools를 사용해 생성한다
• idx를 선택했다면 다음 재귀에서는 idx+1 부터 반복문을 돌아야 경우의 수가 겹치지 않는다

itertools

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

dfs

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        
        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()
            
            return
        
        dfs([], 1, k)
        
        return results