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:

• 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]]

Steps to Solve

1. Sort the candidates: Sorting allows us to easily skip duplicate numbers and avoid generating duplicate combinations.

2. Backtracking: Use a recursive backtracking approach. At each step:

   • Choose a candidate number.
   • Add it to the current combination.
   • Recursively explore combinations using the remaining candidates.
   • Remove the chosen number (backtracking step) to explore other possibilities.

3. Skip Duplicates: After selecting a number, skip subsequent occurrences of that same number to avoid duplicates.

4. Base Cases:

   • If the current sum equals the target, add the current combination to the result.
   • If the current sum exceeds the target, backtrack.

Explanation

The code uses a recursive helper function backtrack. It takes the index of the current candidate, the current combination, and the remaining sum as input. The sorting ensures that duplicate candidates are handled efficiently. The skip variable elegantly skips duplicate candidates in a given recursion level.

Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSumII {

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates); // Sort for easy duplicate handling
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int target, int index, List<Integer> combination, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(combination)); // Found a valid combination
            return;
        }

        if (target < 0 || index >= candidates.length) {
            return; // Target exceeded or no more candidates
        }

        // Include current candidate
        combination.add(candidates[index]);
        backtrack(candidates, target - candidates[index], index + 1, combination, result);
        combination.remove(combination.size() - 1); // Backtrack

        // Skip duplicate candidates
        int skip = index + 1;
        while (skip < candidates.length && candidates[skip] == candidates[index]) {
            skip++;
        }
        backtrack(candidates, target, skip, combination, result);
    }

    public static void main(String[] args) {
        CombinationSumII solution = new CombinationSumII();
        int[] candidates1 = {10, 1, 2, 7, 6, 1, 5};
        int target1 = 8;
        System.out.println(solution.combinationSum2(candidates1, target1)); // Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

        int[] candidates2 = {2, 5, 2, 1, 2};
        int target2 = 5;
        System.out.println(solution.combinationSum2(candidates2, target2)); // Output: [[1, 2, 2], [5]]
    }
}

Complexity

• Time Complexity: O(2^N * K), where N is the number of candidates and K is the average length of combinations. The exponential complexity arises from the backtracking nature of the algorithm. In the worst case, it explores all possible subsets.

• Space Complexity: O(N) in the worst case, due to the recursive call stack and the maximum length of a combination. The space used by the result list is not considered in this analysis, as it is part of the output.