LeetCode Combination Sum (JavaScript), BackTracking

링크 : https://leetcode.com/problems/combination-sum/description/

문제 설명

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1
Output: []

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

---

문제 풀이

백트래킹(dfs)을 이용하여 문제 풀이

1. dfs param : index (탐색할 위치), sum (총 합), selected (선택된 값)

2. sum === target 이라면 answer에 selected을 복사하여 push

• 복사하여 push 하는 이유 : array의 경우 call by reference로 참조 값을 push하게 됨.
• 즉, 이후 push 했던 selected가 변하면 answer의 selected도 변함 -> 따라서 참조 값이 달라지도록 새로 만들어 push

3. 반복문 로직

• 시작지점은 같은 숫자를 사용할 수 있으므로 dfs에 현재 index부터 검사 시작 (자기자신을 다시 탐색할 수 있도록)
• 또한, sum + candidates[i] 가 target보다 클 경우 탐색할 필요가 없으므로 탐색을 시작하지 않음 (백트래킹)

아래 코드에서 if 문으로 처리를 했지만 백트래킹을 좀 더 쉽게 파악하려면
if (sum + candidates[i] <= target) 대신
dfs함수 내부에 if (sum > target) return; 을 추가 해주면 됨
즉, 더이상 진행할 필요가 없다면 종료하도록 (백트래킹)

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    const answer = [];

    const dfs = (index, sum, selected) => {
        if (sum === target) {
            answer.push([...selected]);
            return;
        }

       for (let i = index; i < candidates.length; i++) {
            if (sum + candidates[i] <= target) {
                selected.push(candidates[i]);
                dfs(i, sum + candidates[i], selected);
                selected.pop(candidates[i]);
            }
       }
    }

    dfs(0, 0, []);

    return answer;
};

---

결론

시작하는 지점 (자기 자신을 다시 선택할 수 있으므로 index설정 주의)과 백트래킹을 이용하여 유요한 범위내에서 검사할 수 있도록 지정

추가로 최종적으로 답을 push할 땐 복사하여 같은 참조 값을 넣지 않도록 주의