Distinct sum combinations

You are midway through a Bloomberg phone screen when the interviewer asks you to find all unique combinations of numbers from a list that add up to a target value. The catch: each number can only be used once, and the input list might contain duplicates. This problem, also known as Combination Sum II on other platforms, sits at the intersection of backtracking and careful duplicate handling. It is a favorite at companies like Adobe, Microsoft, Bloomberg, and Amazon because it tests whether you can adapt a standard recursion template to handle real-world messiness.

TL;DR

Sort the candidates array first. Use backtracking to explore all subsets, passing an incremented start index at each recursion level so no candidate is reused. Skip duplicate values at the same recursion level with the check if i > start && candidates[i] == candidates[i - 1]. Break early when a candidate exceeds the remaining target. This produces all distinct combinations in O(2^n) time and O(n) space.

Why This Problem Matters

Backtracking is one of those patterns that keeps showing up in interviews, and for good reason. It tests whether you can systematically explore a search space without missing possibilities or producing duplicates. Distinct Sum Combinations adds an extra layer of difficulty on top of basic combination generation: you have to deal with repeated elements in the input while still producing only unique output combinations. Once you internalize the sort-then-skip pattern used here, you will recognize it in dozens of related problems, from permutations with duplicates to subset generation.

Understanding the Problem

Let's break down what we're being asked to do:

Given: An array of candidate numbers and a target integer Task: Find all unique combinations where the candidates sum to the target Constraints: Each candidate can be used at most once per combination. The result must not contain duplicate combinations.

Here's the primary example:

combinationSum2([10, 1, 2, 7, 6, 1, 5], 8)
=> [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

Notice that the input has two 1s. The combination [1, 1, 6] uses both of them, which is valid since they are at different positions. But we must not produce [1, 1, 6] twice. That is the central challenge.

Edge Cases to Consider

1. No valid combinations: If no subset sums to the target, return an empty list
2. Single element: If the only candidate equals the target, return [[candidate]]
3. All duplicates: [1, 1, 1, 1, 1] with target 3 should produce [[1, 1, 1]] exactly once
4. Large candidate exceeding target: Candidates bigger than the target are pruned immediately

The Sorting Step

The first thing we do is sort the candidates. This is not optional.

The original input: [10, 1, 2, 7, 6, 1, 5]

After sorting:

After sorting: [1, 1, 2, 5, 6, 7, 10]. The two 1s are now adjacent.

Sorting gives us two benefits. First, duplicate values end up next to each other, so we can skip them with a simple comparison to the previous element. Second, once we hit a candidate that is larger than the remaining target, every candidate after it will be larger too, so we can stop the loop early.

Solution Approach

The core idea is standard backtracking with three additions on top of basic subset enumeration:

1. Start index: Pass i + 1 (not i) to the recursive call, preventing a candidate from being reused
2. Duplicate skipping: When candidates[i] == candidates[i - 1] and i > start, skip that candidate
3. Early termination: When candidates[i] > target, break out of the loop

How Duplicate Skipping Works

This is the trickiest part, so let's look at it carefully.

When we are at a given recursion level, we iterate through candidates starting from start. If index i has the same value as index i - 1, and i > start, that means we already explored a branch using that value at this level. Processing it again would produce duplicate combinations in the output. The condition i > start (not i > 0) is critical, because it still allows the first occurrence to be chosen.

The Backtracking Tree

Here is a partial view of the decision tree for [1, 1, 2, 5, 6, 7, 10] with target 8. Each node shows the current path and remaining target.

Every leaf node where the target reaches 0 is a valid combination. The tree is pruned aggressively: any branch where the next candidate exceeds the remaining target is cut off entirely.

Tracing One Path

Let's follow the path that discovers [1, 1, 6]:

The algorithm adds 1 to the path (target drops to 7), adds another 1 (target drops to 6), then adds 6 (target drops to 0, which is a valid combination). It records [1, 1, 6], then backtracks by removing 6, and continues exploring other candidates from that point.

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.*;

public class Solution {
  public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates);
    backtrack(candidates, target, 0, new ArrayList<>(), result);
    return result;
  }

  private void backtrack(int[] candidates, int target, int start,
                         List<Integer> current, List<List<Integer>> result) {
    if (target == 0) {
      result.add(new ArrayList<>(current));
      return;
    }
    for (int i = start; i < candidates.length; i++) {
      // Skip duplicates at the same recursion level
      if (i > start && candidates[i] == candidates[i - 1]) continue;
      // Early termination: all remaining candidates are too large
      if (candidates[i] > target) break;
      // Choose
      current.add(candidates[i]);
      // Explore (i + 1 ensures each candidate used at most once)
      backtrack(candidates, target - candidates[i], i + 1, current, result);
      // Unchoose
      current.remove(current.size() - 1);
    }
  }
}

Let's walk through the key decisions in this code:

1. Sorting first with Arrays.sort(candidates) groups duplicates together and enables both the skip condition and the early break.

2. The base case checks target == 0. When we reach it, we clone the current path into the result. The clone is important because current is mutated throughout the recursion.

3. The skip condition if (i > start && candidates[i] == candidates[i - 1]) prevents duplicate combinations. At a given recursion depth, we only want to explore each distinct value once.

4. Early termination with if (candidates[i] > target) break prunes the search tree significantly. Because the array is sorted, if the current candidate exceeds the target, every subsequent candidate will too.

5. Passing i + 1 to the recursive call ensures each element is used at most once per combination.

Complexity Analysis

Time Complexity: O(2^n)

In the worst case, the algorithm explores every possible subset of the n candidates. Each candidate is either included or excluded, giving 2^n potential combinations. Sorting takes O(n log n), which is dominated by the exponential exploration. In practice, sorting plus early termination prune a large portion of the search space, so the algorithm performs much better than 2^n on most inputs.

Space Complexity: O(n)

The recursion stack can go at most n levels deep (when every candidate is included). The current path also holds at most n elements. The output list of valid combinations is not counted as auxiliary space, since it is the required output.

Why Backtracking, Not DP?

Dynamic programming can count how many combinations sum to a target, but it cannot efficiently enumerate them. Backtracking naturally builds each combination element by element, making it the right tool when you need the actual lists.

Common Pitfalls

Here are mistakes I've seen candidates make with this problem:

1. Forgetting to sort: Without sorting, the duplicate skip condition candidates[i] == candidates[i - 1] does not work. You will get duplicate combinations in the output.

2. Using i > 0 instead of i > start: This is a subtle but critical difference. Using i > 0 would prevent ever using the same value twice across any level, which is too aggressive. The condition must be i > start to allow picking the value at position start while skipping later duplicates at the same level.

3. Passing i instead of i + 1: This mistake allows reusing the same element, turning this into a different problem (Combination Sum I where unlimited reuse is allowed).

4. Not copying the path when adding to results: If you do result.add(current) instead of result.add(new ArrayList<>(current)), all entries in the result end up pointing to the same (eventually empty) list.

5. Missing the early break: Without if (candidates[i] > target) break, the algorithm still produces correct results but wastes time exploring branches that can never succeed.

Interview Tips

When solving this problem in an interview:

1. Clarify constraints: "Can the input contain duplicates? Can each element be used more than once? Should the output combinations be unique?" These questions demonstrate precision.

2. Mention sorting upfront: Explain that sorting is the key enabler for both duplicate handling and early termination.

3. Draw the recursion tree: Even a small sketch with 3-4 candidates shows the interviewer that you understand the branching structure and where pruning happens.

4. Compare with related problems: Mentioning that this is a variation of Combination Sum (with the added constraint of single-use candidates) shows breadth of knowledge.

5. Discuss time complexity honestly: O(2^n) sounds bad, but explain that the pruning makes it practical for the given constraints (n up to 100, values up to 50, target up to 30).

Key Takeaways

• Sort the input first to enable both duplicate skipping and early termination. These two optimizations are not optional; they are essential for correctness and performance.
• The duplicate-skipping condition i > start && candidates[i] == candidates[i - 1] is the heart of this problem. Understand why i > start and not i > 0.
• Pass i + 1 (not i) to the recursive call so each candidate is used at most once per combination.
• Copy the current path before adding it to the results. Mutation during backtracking will otherwise corrupt your stored combinations.
• The choose/explore/unchoose pattern is a reusable template. Once you master it here, you can apply it to permutations, subsets, N-Queens, and many other backtracking problems.

Practice Makes Perfect

Once you have this problem down, try these related backtracking challenges to solidify the pattern:

• Sum Combinations with Repeats (Combination Sum I, where each candidate can be reused)
• Power Set Exploration (generate all subsets of a set)
• Generate Combinations of Parentheses (backtracking with a different constraint)
• Recover IP Addresses (backtracking with string parsing)

This problem and thousands of others are available on Firecode, where over 50,000 users have prepared for technical interviews and landed six and seven-figure jobs at top tech companies. Consistent practice with problems like this is what separates candidates who pass from those who don't.

Solutions in Other Languages

Python

class Solution:
    def combination_sum2(self, candidates, target):
        def backtrack(start, target, path):
            if target == 0:
                result.append(path[:])
                return
            if target < 0:
                return
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                if candidates[i] > target:
                    break
                path.append(candidates[i])
                backtrack(i + 1, target - candidates[i], path)
                path.pop()

        candidates.sort()
        result = []
        backtrack(0, target, [])
        return result

JavaScript

class Solution {
  combinationSum2(candidates, target) {
    candidates.sort((a, b) => a - b);
    const results = [];

    const backtrack = (start, target, path) => {
      if (target === 0) {
        results.push([...path]);
        return;
      }
      for (let i = start; i < candidates.length; i++) {
        if (i > start && candidates[i] === candidates[i - 1]) continue;
        if (candidates[i] > target) break;
        path.push(candidates[i]);
        backtrack(i + 1, target - candidates[i], path);
        path.pop();
      }
    };

    backtrack(0, target, []);
    return results;
  }
}

TypeScript

class Solution {
  combinationSum2(candidates: number[], target: number): number[][] {
    candidates.sort((a, b) => a - b);
    const results: number[][] = [];

    const backtrack = (start: number, remaining: number, path: number[]): void => {
      if (remaining === 0) {
        results.push([...path]);
        return;
      }
      for (let i = start; i < candidates.length; i++) {
        if (i > start && candidates[i] === candidates[i - 1]) continue;
        if (candidates[i] > remaining) break;
        path.push(candidates[i]);
        backtrack(i + 1, remaining - candidates[i], path);
        path.pop();
      }
    };

    backtrack(0, target, []);
    return results;
  }
}

C++

#include <vector>
#include <algorithm>

class Solution {
public:
  std::vector<std::vector<int>> combinationSum2(std::vector<int> &candidates, int target) {
    std::vector<std::vector<int>> result;
    std::vector<int> combination;
    std::sort(candidates.begin(), candidates.end());
    backtrack(candidates, target, 0, combination, result);
    return result;
  }

private:
  void backtrack(const std::vector<int> &candidates, int target, int start,
                 std::vector<int> &combination, std::vector<std::vector<int>> &result) {
    if (target == 0) {
      result.push_back(combination);
      return;
    }
    for (int i = start; i < candidates.size(); ++i) {
      if (i > start && candidates[i] == candidates[i - 1]) continue;
      if (candidates[i] > target) break;
      combination.push_back(candidates[i]);
      backtrack(candidates, target - candidates[i], i + 1, combination, result);
      combination.pop_back();
    }
  }
};

Go

package solution

import "sort"

func CombinationSum2(candidates []int, target int) [][]int {
    var result [][]int
    sort.Ints(candidates)
    var backtrack func(start int, target int, path []int)
    backtrack = func(start int, target int, path []int) {
        if target == 0 {
            combination := make([]int, len(path))
            copy(combination, path)
            result = append(result, combination)
            return
        }
        for i := start; i < len(candidates); i++ {
            if i > start && candidates[i] == candidates[i-1] {
                continue
            }
            if candidates[i] > target {
                break
            }
            backtrack(i+1, target-candidates[i], append(path, candidates[i]))
        }
    }
    backtrack(0, target, []int{})
    return result
}

Scala

class Solution {
  def combinationSum2(candidates: Array[Int], target: Int): List[List[Int]] = {
    def backtrack(start: Int, target: Int, path: List[Int],
                  result: List[List[Int]]): List[List[Int]] = {
      if (target == 0) {
        path :: result
      } else if (target < 0) {
        result
      } else {
        (start until candidates.length).foldLeft(result) { (acc, i) =>
          if (i > start && candidates(i) == candidates(i - 1)) acc
          else backtrack(i + 1, target - candidates(i), candidates(i) :: path, acc)
        }
      }
    }

    val sortedCandidates = candidates.sorted
    backtrack(0, target, Nil, Nil)
  }
}

Kotlin

class Solution {
    fun combinationSum2(candidates: IntArray, target: Int): List<List<Int>> {
        val result = mutableListOf<MutableList<Int>>()
        candidates.sort()
        backtrack(candidates, target, 0, mutableListOf(), result)
        return result
    }

    private fun backtrack(
        candidates: IntArray, target: Int, start: Int,
        current: MutableList<Int>, result: MutableList<MutableList<Int>>
    ) {
        if (target == 0) {
            result.add(current.toMutableList())
            return
        }
        for (i in start until candidates.size) {
            if (i > start && candidates[i] == candidates[i - 1]) continue
            if (candidates[i] > target) break
            current.add(candidates[i])
            backtrack(candidates, target - candidates[i], i + 1, current, result)
            current.removeAt(current.lastIndex)
        }
    }
}

Ruby

class Solution
  def combination_sum2(candidates, target)
    result = []
    candidates.sort!
    backtrack(candidates, target, 0, [], result)
    result
  end

  private

  def backtrack(candidates, target, start, current, result)
    if target == 0
      result << current.dup
      return
    end
    (start...candidates.length).each do |i|
      next if i > start && candidates[i] == candidates[i - 1]
      break if candidates[i] > target
      current << candidates[i]
      backtrack(candidates, target - candidates[i], i + 1, current, result)
      current.pop
    end
  end
end

Rust

impl Solution {
    pub fn combination_sum2(&self, candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        let mut candidates = candidates;
        candidates.sort();
        Self::backtrack(&candidates, target, 0, &mut Vec::new(), &mut result);
        result
    }

    fn backtrack(candidates: &[i32], target: i32, start: usize,
                 current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
        if target == 0 {
            result.push(current.clone());
            return;
        }
        for i in start..candidates.len() {
            if i > start && candidates[i] == candidates[i - 1] { continue; }
            if candidates[i] > target { break; }
            current.push(candidates[i]);
            Self::backtrack(candidates, target - candidates[i], i + 1, current, result);
            current.pop();
        }
    }
}

Swift

class Solution {
    func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
        var result: [[Int]] = []
        let sortedCandidates = candidates.sorted()
        var current: [Int] = []
        backtrack(sortedCandidates, target, 0, &current, &result)
        return result
    }

    private func backtrack(_ candidates: [Int], _ target: Int, _ start: Int,
                           _ current: inout [Int], _ result: inout [[Int]]) {
        if target == 0 {
            result.append(current)
            return
        }
        for i in start..<candidates.count {
            if i > start && candidates[i] == candidates[i - 1] { continue }
            if candidates[i] > target { break }
            current.append(candidates[i])
            backtrack(candidates, target - candidates[i], i + 1, &current, &result)
            current.removeLast()
        }
    }
}

Dart

class Solution {
  List<List<int>> combinationSum2(List<int> candidates, int target) {
    List<List<int>> result = [];
    candidates.sort();
    _backtrack(candidates, target, 0, [], result);
    return result;
  }

  void _backtrack(List<int> candidates, int target, int start,
                  List<int> current, List<List<int>> result) {
    if (target == 0) {
      result.add(List.from(current));
      return;
    }
    for (int i = start; i < candidates.length; i++) {
      if (i > start && candidates[i] == candidates[i - 1]) continue;
      if (candidates[i] > target) break;
      current.add(candidates[i]);
      _backtrack(candidates, target - candidates[i], i + 1, current, result);
      current.removeLast();
    }
  }
}

C#

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

    private void Backtrack(int[] candidates, int target, int start,
                           List<int> current, List<List<int>> result) {
        if (target == 0) {
            result.Add(new List<int>(current));
            return;
        }
        for (int i = start; i < candidates.Length; i++) {
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            if (candidates[i] > target) break;
            current.Add(candidates[i]);
            Backtrack(candidates, target - candidates[i], i + 1, current, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

PHP

class Solution {
    public function combinationSum2(array $candidates, int $target): array {
        $result = [];
        sort($candidates);
        $this->backtrack($candidates, $target, 0, [], $result);
        return $result;
    }

    private function backtrack(array $candidates, int $target, int $start,
                               array $current, array &$result): void {
        if ($target === 0) {
            $result[] = $current;
            return;
        }
        for ($i = $start; $i < count($candidates); $i++) {
            if ($i > $start && $candidates[$i] === $candidates[$i - 1]) continue;
            if ($candidates[$i] > $target) break;
            $current[] = $candidates[$i];
            $this->backtrack($candidates, $target - $candidates[$i], $i + 1, $current, $result);
            array_pop($current);
        }
    }
}