216. Combination Sum III

216. Combination Sum III

Medium

---

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.

 

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.

 

Constraints:

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

이 문제는 합이 n이고..! 조합의 길이가 k인 경우를 찾는 문제입니다.

문제 풀이 방식은 이전 게시물과 동일하나 추가로

조합의 길이가 k와 같은지만 추가해주면 되는 문제입니다.

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function(k, n) {
    const backtrack = (path, sum, start) => {
        if(sum === n && path.length === k){
            ans.push([...path])
            return
        }
        for(let i=start; i<=9; i++){
            if(sum + i > n) continue
            path.push(i)
            backtrack(path, sum+i, i+1)
            path.pop()
        }
    }
    
    const ans = [] 
    backtrack([],0,1)
    
    return ans
};