Combination Sum II medium

Problem Statement

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 that 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]] Explanation: 1 + 1 + 6 = 8 1 + 2 + 5 = 8 1 + 7 = 8 2 + 6 = 8

Example 2:

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

Steps:

1. Sort the input array: Sorting allows us to easily skip duplicate numbers and optimize the search.
2. Backtracking: Use a recursive backtracking function to explore all possible combinations.
3. Base Case: If the current sum equals the target, add the current combination to the result.
4. Recursive Step: For each number in the sorted array:
   • If the number is greater than the target, we can skip it (since the array is sorted).
   • If the number is less than or equal to the target:
     • Add the number to the current combination.
     • Recursively call the function with the remaining numbers (skipping duplicates).
     • Remove the number from the current combination (backtracking).
5. Skip Duplicates: When iterating through the array, skip duplicate numbers to avoid generating duplicate combinations.

Explanation:

The backtracking approach systematically explores all possible combinations by recursively adding and removing numbers from the current combination. Sorting the input array is crucial for efficiently skipping duplicate numbers. The skipDuplicates mechanism ensures that we only consider unique combinations in the result.

Code:

function combinationSum2(candidates: number[], target: number): number[][] {
    const result: number[][] = [];
    candidates.sort((a, b) => a - b); // Sort the candidates

    function backtrack(combination: number[], remaining: number, start: number) {
        if (remaining === 0) {
            result.push([...combination]); // Found a combination
            return;
        }

        if (remaining < 0) {
            return; // No need to explore further
        }

        for (let i = start; i < candidates.length; i++) {
            // Skip duplicate numbers
            if (i > start && candidates[i] === candidates[i - 1]) {
                continue;
            }

            combination.push(candidates[i]);
            backtrack(combination, remaining - candidates[i], i + 1); // Explore further
            combination.pop(); // Backtrack: remove the last added number
        }
    }

    backtrack([], target, 0);
    return result;
}


//Example usage
const candidates1 = [10, 1, 2, 7, 6, 1, 5];
const target1 = 8;
const result1 = combinationSum2(candidates1, target1);
console.log(result1); // Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

const candidates2 = [2, 5, 2, 1, 2];
const target2 = 5;
const result2 = combinationSum2(candidates2, target2);
console.log(result2); // Output: [[1, 2, 2], [5]]

Complexity:

• Time Complexity: O(2^N * N), where N is the length of candidates. In the worst case, we might explore all possible subsets. The N factor comes from adding/removing elements to the combination array.
• Space Complexity: O(N) in the worst case, due to the recursive call stack depth and the size of the combination array. The result array's size can also grow significantly in the worst case.