[LeetCode/Javascript] 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.

 

Example 1:

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

Example 2:

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

Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations.
Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

 

Constraints:

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

 

 

 

 

 

해결과정

처음에는 합계인 n을 기준으로 1부터 기준을 잡아서 하나씩 빼서 sum이 0이 되면 그 숫자들만 반환하면 되지 않을까? 라고 생각했다. 하지만 접근법이 맞을지언정 코드로 어떻게 풀어내야 할지 감이 하나도 안 잡혔다. 

 

머릿속에는

1. for문같이 loop를 해야한다는 생각

2. loop하면서 k 길이까지 채웠을 때 숫자요소들을 만들어 놓은 []에 넣어야한다는 생각

3. 재귀함수가 필요할 것 같다는 생각

이 세가지 생각이 들었는데 어떻게 구현해야하는 건지 머릿속이 복잡했다. 

한참을 그림을 그리며 생각하다가 back-tracking 이라는 문제타입에 대해 검색을 해봤고, 그 이후에 솔루션 강의를 찾아봤다. 

 

 

 

백트래킹(Back-Tracking)

• 백트래킹은 문제의 조건에 따라 탐색해야 하는 모든 경우의 수를 시도하면서 해를 찾는 알고리즘. 주로 DFS(깊이 우선 탐색)와 함께 사용되며, 재귀 함수를 통해 구현.
• 모든 경우의 수에서 조건을 만족하는 경우를 탐색하는 것이기 때문에 완전탐색기법인 DFS(깊이우선탐색), BFS(너비우선탐색)로 모두 구현이 가능
• DFS(깊이우선탐색) 은 사전에 불필요한 조건 차단을 하지 않고 진행해서 다 돌지만, 백트래킹은 불필요한 조건을 차단하고 필요한 것들 안에서 탐색을 진행, 실행속도를 향상할 수 있습니다.

 

 

 

 

 

 

코드

var combinationSum3 = function(k, n) {
    let result = []
    
    const nums = [];
    for(let i=1; i<10; i++) nums.push(i)

    const dfs = (index, nums, cur, k, total) =>{
        if(total < 0) return;
        
        if(cur.length === k){
            if(total == 0){
                 result.push(cur.slice());
            }
            return
        }
        
        for(let i = index; i<nums.length ; i++ ){
          cur.push(nums[i]);
          // 현재 index에 다음값, 현재, 구해야하는 합에서 현재index빼기
          dfs(i+1, nums, cur, k, total - nums[i]);
          cur.pop();
        }
        
    }
    
    dfs(0, nums, [], k, n)
    return result
};