AlgoMaster Logo

Combination Sum II

mediumFrequency8 min readUpdated June 23, 2026

Understanding the Problem

We're given an array of numbers that may contain duplicates, and we need to find all unique combinations that add up to a target sum. Each element in the array can be used at most once (based on its position), and we can't have duplicate combinations in the result.

Two requirements interact here. The search must explore subsets that sum to a target, and the input can contain duplicate values, so naive backtracking produces the same combination through different index paths. For example, with candidates = [1, 1, 2] and target = 3, picking the first 1 with 2 and picking the second 1 with 2 both give [1, 2], but the result should contain it once.

Sorting the array places equal values next to each other. That lets the backtracking skip a value it has already tried at the same decision level, which is enough to prevent duplicate combinations from being generated at all.

Key Constraints:

  • 1 <= candidates.length <= 100 → With n up to 100, we can't enumerate all 2^100 subsets. But the target is at most 30, and each candidate is at least 1, so any valid combination has at most 30 elements. This keeps the recursion tree shallow.
  • 1 <= candidates[i] <= 50 → All candidates are positive. This means the running sum only increases as we add elements, allowing us to prune when the sum exceeds the target.
  • 1 <= target <= 30 → The small target limits the number of valid combinations. Even though the array can have 100 elements, we'll never go deeper than 30 levels in the recursion.

Approach 1: Brute Force (Generate All, Then Deduplicate)

Intuition

Ignore duplicates during generation and remove them afterward. Sort the array, generate every subset that sums to the target with standard include/exclude backtracking, and store each valid combination in a set so repeated combinations collapse into one entry.

Sorting matters even in this brute-force version. The recursion picks elements in index order, so on an unsorted array two index subsets with the same values can produce differently ordered lists ([7, 1] from one path, [1, 7] from another), and the set would treat them as distinct. Sorting first gives every combination a canonical order, so equal combinations compare equal.

The cost is wasted work: the search builds duplicate combinations in full, and the set immediately discards them.

Algorithm

  1. Sort the candidates array.
  2. Use backtracking to explore all subsets: for each element, try including it and try skipping it.
  3. When the remaining target reaches 0, add the current combination to a set (to catch duplicates).
  4. When the remaining target goes negative, stop exploring that branch.
  5. Convert the set of unique combinations into a list and return it.

Example Walkthrough

1Start: include/exclude each element, target=8
0
1
index
1
1
2
2
3
5
4
6
5
7
6
10
1/8

Code

The set exists only to discard combinations that were generated more than once. The next approach avoids generating them in the first place.

Approach 2: Backtracking with Sorting and Duplicate Skipping

Intuition

Sort the array and apply one rule during backtracking: at any given decision level, once a value has been tried, skip every later occurrence of that same value.

After sorting, duplicates sit next to each other. Each call loops over candidates from its start index to the right, so when i > start and candidates[i] == candidates[i-1], the value at index i was already tried at this level by the iteration at i-1, and the loop skips it.

Algorithm

  1. Sort the candidates array.
  2. Start a backtracking function with a start index, the remaining target, and the current combination.
  3. If remaining equals 0, we found a valid combination. Add a copy to the result.
  4. Loop from start to the end of the array. For each index i:
    • If candidates[i] exceeds the remaining target, break (all subsequent candidates are larger due to sorting).
    • If i > start and candidates[i] == candidates[i-1], skip this candidate (duplicate at the same level).
    • Add candidates[i] to the current combination.
    • Recurse with i + 1 as the new start and remaining - candidates[i] as the new target.
    • Remove the last element (backtrack).
  5. Return the result.

Example Walkthrough

1Start: backtrack(start=0, remaining=8, current=[])
0
1
start
1
1
2
2
3
5
4
6
5
7
6
10
1/11

Code

A different way to handle duplicates works at the level of values instead of indices.

Approach 3: Backtracking with Frequency Counting

Intuition

Count how many times each value appears, then backtrack over the unique values. For each unique value, decide how many copies to use (from 0 up to the available count), then move to the next unique value.

This reframes the problem from "which indices to pick" to "how many of each value to use," and no duplicate-skipping rule is needed because the search never sees the same value twice at one level. The deduplication argument is direct: two combinations produced by this search must differ in the copy count of at least one value, so they cannot be equal.

Algorithm

  1. Count the frequency of each candidate value (using a hash map or sorted map).
  2. Convert the frequency map into a list of (value, count) pairs.
  3. Start a backtracking function that iterates over these pairs. For each pair (value, count):
    • Try using 0 copies, 1 copy, 2 copies, ..., up to count copies, stopping the loop as soon as value * copies exceeds the remaining target.
    • After choosing how many copies to use, recurse to the next pair.
    • Remove the added copies (backtrack).
  4. When the remaining target reaches 0, record the combination.

Example Walkthrough

1Frequency count: {1:1, 2:3, 5:1}. Start with value=1
1
:
1
2
:
3
5
:
1
1/10

Code