[LeetCode] 40. Combination Sum II

https://leetcode.com/

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

 

Code :

var combinationSum2 = function(candidates, target) {
    const result = []; // 조합들을 저장할 배열
    const used = Array(candidates.length).fill(false); // 사용된 숫자를 추적하는 배열

    candidates.sort((a, b) => a - b); // candidates 배열을 정렬합니다.

    // 백트래킹 함수 정의
    function backtrack(remaining, currentCombo, start) {
        if (remaining === 0) {
            result.push([...currentCombo]); // 합이 목표값과 일치하는 경우 결과에 추가
            return;
        }

        if (remaining < 0) {
            return;
        }

        // candidates 배열을 순회하며 조합을 탐색합니다.
        for (let i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] === candidates[i - 1] && !used[i - 1]) {
                continue; // 중복된 숫자를 건너뜁니다.
            }
            currentCombo.push(candidates[i]);
            used[i] = true;
            backtrack(remaining - candidates[i], currentCombo, i + 1); // 재귀 호출로 조합 탐색
            currentCombo.pop(); // 조합에서 숫자를 제거합니다.
            used[i] = false;
        }
    }
    backtrack(target, [], 0); // 백트래킹 함수 호출
    return result; // 찾은 조합들을 반환합니다.
};

 

Solutions Code :

var combinationSum2 = function(candidates, target) {
    candidates = candidates.sort((a, b) => a - b); // 배열을 오름차순으로 정렬합니다.
    const output = []; // 조합을 저장할 배열
    const hashmap = new Map(); // 중복된 조합을 처리하기 위한 맵

    // 백트래킹 함수 정의
    const backtracking = (curr, remaining, target) => {
        if (target < remaining[0] || !remaining.length) return; // 남은 숫자로 target을 만들 수 없는 경우 종료
        const checkedHashmap = new Map(); // 중복된 숫자를 처리하기 위한 맵
        for (let i = 0; i < remaining.length; i++) {
            const number = remaining[i];
            if (checkedHashmap.has(number)) continue; // 중복된 숫자를 처리합니다.
            if (number > target) return; // 타겟보다 큰 숫자는 제외합니다.
            const newRemaining = [...remaining]; // 남은 숫자들의 복사본을 생성합니다.
            const newCurr = [...curr]; // 현재 조합의 복사본을 생성합니다.
            newCurr.push(number); // 현재 숫자를 조합에 추가합니다.
            newRemaining.splice(i, 1); // 현재 숫자를 남은 숫자에서 제거합니다.
            if (target - number === 0) {
                const key = newCurr.sort((a, b) => a - b).toString(); // 중복된 조합인지 확인하기 위한 키를 생성합니다.
                if (hashmap.has(key)) return; // 이미 존재하는 조합인 경우 처리합니다.
                hashmap.set(key, 1); // 새로운 조합을 맵에 추가합니다.
                return output.push(newCurr); // 새로운 조합을 결과 배열에 추가합니다.
            }
            checkedHashmap.set(number, 1); // 중복된 숫자를 처리하기 위해 맵에 추가합니다.
            backtracking(newCurr, newRemaining, target - number); // 재귀 호출로 조합 탐색을 진행합니다.
        }
    }
    backtracking([], candidates, target); // 백트래킹 함수 호출
    return output; // 찾은 조합들을 반환합니다.
};

 

 

출처 : https://leetcode.com/problemset/all/

Problems - LeetCode