LeetCode Combination Sum || (JavaScript), BackTracking

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

문제 설명

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

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

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

---

문제 풀이

https://kuh97.tistory.com/entry/LeetCode-Combination-Sum-JavaScript-BackTracking

LeetCode Combination Sum (JavaScript), BackTracking

위 사이트 설명 참고

+ 추가 된 내용

• 후보는 한 번씩만 선택되어야 되고 중복이 되면 안된다. -> 시작지점 부터 검사를 진행할 때 그 이후에 같은 숫자가 나오면 건너뛰도록 해야 중복된 값이 안나옴
• Output은 정렬이 되어 있다. -> 처음에 candidates를 sort

 

중복된 값 예시

[1, 1, 2, 5, 6, 7, 10] / 8인 상황에서

[1, 2, 5] 가 정답으로 만들어지는데 `if (i > index && (candidates[i - 1] === candidates[i])) continue;`를 추가 안하게 되면 다음과 같은 상황에서 중복으로 생성이 됨

• [1, 1, 2, 5, 6, 7, 10]
• [1, 1, 2, 5, 6, 7, 10]

이와 같은 상황을 처리하기위해 같은 depth인 경우 i를 기준으로 i - 1 === i 이번 건너 뛰도록해서 중복을 처리

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    const answer = [];
    candidates.sort((a, b) => a - b);

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

        for (let i = index; i < candidates.length; i++) {
            if (i > index && (candidates[i - 1] === candidates[i])) {
                continue;
            }

            if (sum + candidates[i] <= target) {
                selected.push(candidates[i]);
                backtracking(i + 1, sum + candidates[i], selected);
                selected.pop();
            }
        }
    }

    backtracking(0, 0, []);

    return answer;
};

---

결론

중복된 값을 처리하기 위한 로직을 설정하는게 중요