[LeetCode] 216 | Combination Sum III | Python

---

문제 링크: https://leetcode.com/problems/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.

---

조건

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

---

내 풀이

itertools 라이브러리의 combinations를 사용한다.

주어진 수의 범위가 1~9이므로 combination을 사용해도 시간초과가 나지 않는다.

[1, 2, 3, 4, 5, 6, 7, 8, 9] 리스트 중 combination을 이용해 k개를 뽑고, 그 때의 합이 n인 것만 ans에 추가한다.

---

코드

from itertools import combinations

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        ans = []
        
        com = combinations([x for x in range(1, 10)], k)
        for c in com:
            if sum(c) == n:
                ans.append(c)
                
        return ans