40. Combination Sum II

[mah-shamim]

Topics: Array, Backtracking

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

[mah-shamim]

We can use a backtracking approach. The key idea is to sort the array first to handle duplicates easily and then explore all possible combinations using backtracking.

Let's implement this solution in PHP: 40. Combination Sum II

<?php
function combinationSum2($candidates, $target) {
    sort($candidates);
    $result = [];
    backtrack($candidates, $target, 0, [], $result);
    return $result;
}

function backtrack($candidates, $target, $start, $currentCombination, &$result) {
    if ($target == 0) {
        $result[] = $currentCombination;
        return;
    }
    
    for ($i = $start; $i < count($candidates); $i++) {
        if ($i > $start && $candidates[$i] == $candidates[$i - 1]) {
            continue; // Skip duplicates
        }
        
        if ($candidates[$i] > $target) {
            break; // No need to continue if the candidate exceeds the target
        }
        
        backtrack($candidates, $target - $candidates[$i], $i + 1, array_merge($currentCombination, [$candidates[$i]]), $result);
    }
}

// Example usage:
$candidates1 = [10,1,2,7,6,1,5];
$target1 = 8;
print_r(combinationSum2($candidates1, $target1));

$candidates2 = [2,5,2,1,2];
$target2 = 5;
print_r(combinationSum2($candidates2, $target2));
?>

Explanation:

1. Sorting: The candidates array is sorted to handle duplicates easily and to ensure combinations are formed in a sorted order.
2. Backtracking: The backtrack function is used to explore all possible combinations.
   • If the target becomes zero, we add the current combination to the result.
   • We iterate over the candidates starting from the current index. If a candidate is the same as the previous one, we skip it to avoid duplicate combinations.
   • We subtract the current candidate from the target and recursively call the backtrack function with the new target and the next index.
   • The recursive call continues until we either find a valid combination or exhaust all possibilities.
3. Pruning: If the candidate exceeds the target, we break out of the loop early since further candidates will also exceed the target.

This code will output all unique combinations that sum up to the target while ensuring that each candidate is used only once in each combination.

[basharul-siddike]

Thanks for solving the problem of "Combination Sum II"

[mah-shamim]

Thanks