40. Combination Sum II

Intuition

Like Combination Sum I (unbounded), but each number can only be used once. Sort to enable duplicate skipping: after choosing candidates[i], skip over any later indices j where candidates[j] == candidates[j-1] at the same recursion depth. This prevents identical combinations.

Algorithm

1Sort candidates.
2Backtrack(start, current, remaining):
3If remaining == 0: add current to results.
4For i from start to n-1: if i > start and candidates[i] == candidates[i-1], skip (duplicate).
5If candidates[i] > remaining, break (sorted -> no later element can work).
6Choose candidates[i], recurse with start=i+1 (not i, since each element used once).
7Undo the choice.

Example Walkthrough

Input: candidates = [10,1,2,7,6,1,5], target = 8 -> sorted: [1,1,2,5,6,7,10]

1.Start with []. Choose 1(idx0), recurse: choose 1(idx1) -> [1,1], recurse: choose 6 -> [1,1,6] = 8 .
2.Back at [1,1]: skip 7 (would be [1,1,7]=9>8). Done.
3.Back at [1]: skip idx1 (1==1 dup at same level). Choose 2 -> [1,2], choose 5 -> [1,2,5] = 8 .
4.Also find [2,6] and [1,7].

Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

Common Pitfalls

•The duplicate skip condition `i > start && candidates[i] == candidates[i-1]` uses `start`, not 0 - to allow using the same value at different depth levels.
•Recurse with i+1, not i, to enforce "each element at most once".

40.cs

// Approach: Sort the candidates array first so duplicates are adjacent.
// Use backtracking: for each position, iterate from 'start' to end, subtracting candidates from target.
// Skip duplicate candidates at the same recursion depth (i > start && candidates[i] == candidates[i-1]).
// This prevents generating duplicate combinations without using a hash set.
// Stop exploring a branch early if candidates[i] > remaining target (array is sorted, so all further are larger).
// Time: O(2^n) in the worst case. Space: O(n) for the recursion stack.

public class Solution
{
    public IList<IList<int>> CombinationSum2(int[] candidates, int target)
    {
        IList<IList<int>> ansList = new List<IList<int>>();
        Array.Sort(candidates);
        findCombinations(0, candidates, target, new List<int>(), ansList);
        return ansList;
    }

    private void findCombinations(int ind, int[] array, int target, IList<int> ds, IList<IList<int>> ansList)
    {
        if (target == 0)
        {
            ansList.Add(new List<int>(ds));
            return;
        }

        for (int j = ind; j < array.Length; j++)
        {
            if (j > ind && array[j - 1] == array[j])
                continue;

            if (array[j] > target)
                break;

            ds.Add(array[j]);
            findCombinations(j + 1, array, target - array[j], ds, ansList);
            ds.RemoveAt(ds.Count - 1);
        }
    }
}

Was this solution helpful?