[LEET CODE] 77. Combinations

# Problem

Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]. You may return the answer in any order. Constraints: 1 <= n <= 20 1 <= k <= n

 

# My Answer

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        l = [num for num in range(1,n+1)]
        temp=[]
        result=[]
        new=l
        def dfs(l):
            if len(temp)==k:
                result.append(temp[:])
            for i in range(len(l)):
                new = l[i:]
                new.remove(l[i])
                temp.append(l[i])
                dfs(new)
                temp.pop()
                
        dfs(l)
        return result
        

순열문제와 비슷하지만 조합은 순서에 상관없이 숫자가 한번씩 나오면 되기 때문에

재귀 함수를 호출할 때 현재 인덱스 부터 끝까지의 리스트를 사용

 

# Solution 1 - DFS로 k개 조합 생성

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        results = []

        def dfs(elements, start: int, k: int):
            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

재귀함수를 호출할 때  이전 리스트를 그대로 사용하여 그 뒤에 숫자를 추가시켜 준다

 

 

 

# Solution 2 - itertools 모듈 사용

import itertools

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