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

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

2. Backtracking: Use a recursive backtracking approach to explore all possible combinations.

3. Recursive function: The recursive function takes the following parameters:

   • index: The current index in the candidates array.
   • combination: The current combination being built.
   • remaining: The remaining sum needed to reach the target.

4. Base cases:

   • If remaining is 0, a valid combination is found. Add it to the result list.
   • If remaining is negative or index is out of bounds, backtrack.

5. Recursive step:

   • Include: Recursively call the function with the current number included in the combination (index + 1, updated combination, and updated remaining). Skip duplicate numbers by checking the next element if it's the same.
   • Exclude: Recursively call the function without including the current number (index + 1, unchanged combination, and unchanged remaining).

6. Return: Return the list of unique combinations.

Explanation

The backtracking algorithm systematically explores all possible combinations. Sorting the input array ensures that duplicate combinations are not generated. The skipping of duplicate numbers in the "Include" step is crucial for efficiency and correctness. The base cases handle the termination conditions of the recursion.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
        IList<IList<int>> result = new List<IList<int>>();
        Array.Sort(candidates); //Sort for efficiency and duplicate removal
        Backtrack(candidates, target, 0, new List<int>(), result);
        return result;
    }

    private void Backtrack(int[] candidates, int target, int index, List<int> combination, IList<IList<int>> result) {
        if (target == 0) {
            result.Add(new List<int>(combination)); //Add a copy to avoid modification
            return;
        }

        if (target < 0 || index >= candidates.Length) {
            return;
        }

        // Include
        combination.Add(candidates[index]);
        Backtrack(candidates, target - candidates[index], index + 1, combination, result);
        combination.RemoveAt(combination.Count - 1); //Backtrack: remove the last added element

        // Exclude (Skip duplicates)
        int skipIndex = index + 1;
        while (skipIndex < candidates.Length && candidates[skipIndex] == candidates[index]) {
            skipIndex++;
        }
        Backtrack(candidates, target, skipIndex, combination, result);
    }
}

Complexity

• Time Complexity: O(2^N * k), where N is the number of candidates and k is the average length of combinations. The worst-case scenario is exploring all possible subsets.
• Space Complexity: O(k * x), where k is the average length of combinations and x is the number of combinations. The space is mainly used for the recursion stack and storing the combinations. In the worst case, it could be O(N * 2^N), if all combinations have length N.