[LeetCode] 77. Combinations - 파이썬(Python)

문제 링크 : https://leetcode.com/problems/combinations/

Combinations - LeetCode

유형 : 백트래킹(BackTracking)

문제 설명

두 개의 정수 n, k가 주어질 때 1부터 n까지의 정수들에게 k개를 뽑아 만들 수 있는 모든 조합을 return 하는 문제이다.

Example 1)
Input: n = 4, k = 2
Output: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

Example 2)
Input: n = 1, k = 1
Output: [[1]]

제한사항

• 1 <= n <= 20
• 1 <= k <= n

문제 풀이

성공 코드

from typing import List

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        self.n = n
        self.k = k
        self.nums = range(1, n+1)
        self.combs = []

        self.bt(0, [])
        return self.combs

    def bt(self, index: int, chosen: List[int]):
        if len(chosen) == self.k:
            self.combs.append(chosen.copy())
            return
        
        for i in range(index, self.n):
            chosen.append(self.nums[i])
            self.bt(i+1, chosen)
            chosen.pop()