Leetcode 216. Combination Sum III

문제

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used.
Each number is used at most once.

Return a list of all possible valid combinations. 
The list must not contain the same combination twice, 
and the combinations may be returned in any order.

k개의 숫자로 이루어져 총 합이 n이 되는 숫자의 조합들을 리턴하세요
숫자는 1~9 까지 사용 가능하며, 같은 숫자가 두번이상 쓰여선 안됩니다.

예시

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
다른 조합은 존재하지 않음.

제한

• $2 <= k <= 9$
• $1 <= n <= 60$

풀이법

• 백트래킹을 사용한다.
• 현재까지 구한 합, 추가 가능한 남은 숫자 갯수, 현재까지 완성된 조합, 마지막에 선택한 숫자가 중요시 된다.
• 마지막에 구한 수 + 1 ~ 9에서 다음 숫자를 찾되, 현재까지 완성된 조합에 없는 숫자이면서 현재까지 구한 합에서 더했을때 n보다 작거나 같아야 한다.
  • 마지막 숫자 + 1 ~ 9 에서 다음 조합의 숫자를 구해 중복되는 조합이 없도록 하는것이 중요하다!!
• 마지막 숫자를 구하고 합이 일치하다면 정답 배열에 추가한다.

from typing import Set

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans: List[Set[int]] = [] 

        def backtracking(current_sum: int, num_left: int, ans_set: Set[int], last_number: int):
            nonlocal ans

            for i in range(last_number + 1, 10):
                if i in ans_set or current_sum + i > n:
                    continue
                if num_left == 1 and current_sum + i == n:
                    ans.append(list(ans_set.union({i})))
                else:
                    backtracking(current_sum + i, num_left - 1, ans_set.union({i}), i)

        backtracking(0, k, set(), 0)

        return ans

nonlocal

• 중첩 함수에서 외부 함수의 변수를 가져올때 사용한다.