[리트코드] 77. 조합 (Python)

Combinations - LeetCode

문제

n과 k를 입력받고 1 부터 n까지 숫자의 k개로 만들 수 있는 가능한 모든 조합을 출력해라

과정

1. 조합이란 n개의 원소를 갖는 집합에서 r개의 원소를 선택하는 것 혹은 선택의 결과로 정의된다.
2. 재귀를 이용하여 문제를 풀어준다.

 

입력

n = 4, k = 2

출력

[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

 

풀이

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        
        def dfs(nums, start, k):
            if k == 0:
                result.append(nums[:])
                return
            
            for i in range(start, n+1):
                nums.append(i)
                dfs(nums, i+1, k-1)
                nums.pop()
        
        dfs([], 1, k)
        return result

 

한 줄씩 코드 해석해보기

result = []

• 결과를 출력할 리스트를 생성한다.

def dfs(nums, start, k):
    if k == 0:
        result.append(nums[:])
        return

• 백트래킹 함수 dfs를 만들어준다. 
• nums에는 추가된 숫자, start에는 탐색 시작점, k는 남은 숫자의 개수가 된다.

for i in range(start, n+1):
    nums.append(i)
    dfs(nums, i+1, k-1)
    nums.pop()

• 시작점부터 n+1 까지 for문을 돌린다.
• nums에 1부터 숫자를 추가해준다.
• 그 후 dfs함수에 nums와 그 다음값, 남은 개수를 세기 위해 k-1을 한 값을 넣어준다.
• 재귀가 돌면 nums에서 pop() 해주고 다음값을 본다.

dfs([], 1, k)
return result

• 처음 dfs함수에 들어가는 값은 nums에는 빈 리스트, 시작점 1, 입력받은 k 값이 들어간다.
• result를 반환한다.

 

한 줄 풀이

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

• itretools.combinations(range(1, n+1), k) : 1부터 입력받은 값까지 k개로 이루어진 모든 조합을 반환한다.