Sum Combinations with Repeats

You're in a Microsoft interview and the interviewer pushes a laptop toward you. "Given an array of numbers, find every way to pick from them - with repeats allowed - so they add up to a target." You recognize it right away: this is Combination Sum, one of the most common backtracking problems in technical interviews. On Firecode, we call it "Sum Combinations with Repeats," and it's a staple at companies like Adobe, Bloomberg, and Uber. The twist that makes this problem interesting is the "unlimited reuse" rule - any candidate can appear in a combination as many times as you want.

TL;DR

Use backtracking to explore all possible combinations. At each step, either include the current candidate (subtracting it from the target) or skip to the next one. When the remaining target hits zero, you've found a valid combination. A start index parameter prevents duplicates by ensuring candidates are only picked in non-decreasing order. Time complexity is O(2^target) in the worst case, with O(target) space for the recursion stack.

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

Why This Problem Matters

Combination Sum is the gateway to backtracking problems. The pattern you learn here - build a candidate list, recurse, undo - shows up in permutations, subsets, N-Queens, Sudoku solvers, and dozens of other problems. If you can solve Combination Sum cleanly, you have the template for most backtracking questions an interviewer will throw at you.

The Setup

Given an array of distinct positive integers called candidates and an integer target, find all unique combinations where the chosen numbers sum to target. Each number in candidates can be used an unlimited number of times.

combinationSum([2, 3, 6, 7], 7) => [[2, 2, 3], [7]]
combinationSum([2, 3, 5], 8)    => [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
combinationSum([2], 1)          => []

Constraints

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements in candidates are distinct
• 1 <= target <= 40
• Fewer than 150 unique combinations for any given input

Edge Cases

1. No valid combination: combinationSum([2], 1) returns [] because 2 > 1
2. Single candidate: combinationSum([2], 2) returns [[2]]
3. Large target with small candidates: produces many combinations (but the constraint caps it at 150)
4. Candidate equals target: [7] with target 7 yields [[7]] immediately

The Backtracking Approach

Backtracking is a systematic way to search through all possible combinations. Think of it as exploring a decision tree: at each node, you decide which candidate to add next. If the running total exceeds the target, you prune that branch and try a different path.

There are two decisions at every step:

1. Include the current candidate and recurse with the reduced target
2. Skip to the next candidate and try larger values

The Recursion Tree

Here's what the decision tree looks like for candidates = [2, 3, 6, 7] with target = 7. Green-highlighted nodes represent valid combinations where the remaining target reaches zero:

The algorithm explores depth-first. Starting from the root (target = 7), it picks 2 repeatedly until the remaining target drops below zero, then backtracks and tries the next candidate. The two highlighted leaf nodes correspond to the two valid solutions: [2, 2, 3] and [7].

Avoiding Duplicate Combinations

Without any constraint, the algorithm would generate both [2, 3] and [3, 2] as separate combinations (if the target were 5). The start index solves this. At each level of recursion, the loop begins from the current index, not from zero. This forces candidates to appear in non-decreasing order within each combination.

When you pick candidate at index 0 (value 2), the next recursive call can pick from indices 0, 1, 2, or 3. But when you pick candidate at index 1 (value 3), the next call can only pick from indices 1, 2, or 3. This single rule eliminates all duplicate orderings.

Building a Combination Step by Step

Here's how the algorithm builds the combination [2, 2, 3]:

At each step, a candidate is added to the current combination and the remaining target decreases by that amount. When the remaining target hits zero, the combination is complete.

The Backtrack Step

After finding [2, 2, 3], the algorithm needs to explore other possibilities. It does this by removing the last element and trying the next candidate:

The "remove last element" step is what gives backtracking its name. You undo your most recent choice and try an alternative. This pattern - add, recurse, remove - is the core loop of every backtracking algorithm.

Implementation

Java

import java.util.*;

public class Solution {
  public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    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;
    }
    if (target < 0) {
      return;
    }

    for (int i = start; i < candidates.length; i++) {
      current.add(candidates[i]);
      backtrack(candidates, target - candidates[i], i, current, result);
      current.remove(current.size() - 1);
    }
  }
}

Python

class Solution:
    def combination_sum(self, candidates: list[int], target: int) -> list[list[int]]:
        result = []

        def backtrack(remaining, combo, start):
            if remaining == 0:
                result.append(list(combo))
                return
            if remaining < 0:
                return

            for i in range(start, len(candidates)):
                combo.append(candidates[i])
                backtrack(remaining - candidates[i], combo, i)
                combo.pop()

        backtrack(target, [], 0)
        return result

The logic is the same in both languages. Three moving parts: the base case (target equals zero), the pruning condition (target goes negative), and the loop that tries each candidate from the current index onward.

Walkthrough with a Second Example

For candidates = [2, 3, 5] and target = 8, the recursion tree produces three valid combinations:

The three highlighted leaf nodes correspond to [2, 2, 2, 2], [2, 3, 3], and [5, 3] (stored as [3, 5] in sorted order). Notice how the tree gets deeper when using smaller candidates - four 2s are needed to reach 8, but only two values are needed with 3 and 5.

Complexity Analysis

Time: O(2^target)

In the worst case, the algorithm explores a tree where each level represents a binary choice (include or skip a candidate). The maximum depth is target / min(candidates), since you can keep picking the smallest candidate until the target is consumed. With pruning, the actual running time is much better in practice. The problem guarantees fewer than 150 valid combinations for any input, which keeps the output manageable.

Space: O(target)

The recursion stack depth is bounded by target / min(candidates) - the longest possible combination. The current list also grows up to this length. Together, this gives O(target) auxiliary space. The output list of combinations is separate and depends on the number of valid solutions.

Why Not Dynamic Programming?

You could use DP to count how many combinations sum to the target, but when the problem asks you to enumerate all combinations (not just count them), backtracking is more natural. DP would require additional work to reconstruct the actual lists from the table, and the code ends up more complex without any asymptotic improvement.

Common Pitfalls

1. Forgetting to copy the current combination: When target == 0, you must add a copy of the current list to the result. Adding the list directly means all entries in the result will point to the same (eventually empty) list.

   // Wrong - all result entries share the same reference
   result.add(current);
   
   // Correct - create an independent copy
   result.add(new ArrayList<>(current));
   

2. Missing the start index: Without the start parameter, the algorithm generates permutations instead of combinations. [2, 3] and [3, 2] would both appear as results.

3. Not removing the last element: The current.remove(current.size() - 1) call after the recursive call is what makes backtracking work. Skip it and the combination list keeps growing without ever exploring alternatives.

4. Incorrect base case ordering: Check target == 0 before target < 0. If you check the negative case first, a combination that hits exactly zero might get pruned when the loop tries the next candidate but the base case hasn't been recorded yet. In practice both orderings work for this specific problem, but the "zero first" pattern is clearer and less error-prone.

Interview Tips

When you get this problem in an interview:

1. Clarify the constraints first: "Can candidates contain duplicates? Can candidates be negative? Is the order of combinations significant?" These questions show careful thinking and often reveal whether the interviewer is asking Combination Sum I or II.

2. Start with a small example: Draw the recursion tree for [2, 3] with target 5 on the whiteboard. Trace through 3-4 branches showing how the start index prevents duplicates.

3. Name the pattern: Say "This is a backtracking problem" early. It frames the conversation and shows you recognize the problem category.

4. Explain why you copy: When you add new ArrayList<>(current) to the result, explain that you need a snapshot because the same list object is reused across recursive calls.

5. Discuss follow-ups: Combination Sum II (each element used at most once, duplicates in input), Combination Sum III (exactly k numbers from 1-9), and the subset/permutation family of problems all use the same backtracking template.

Key Takeaways

• Backtracking builds combinations incrementally: add a candidate, recurse with the reduced target, then remove the candidate and try the next one. This add-recurse-remove loop is the template for all backtracking problems.
• The start index is what turns permutation enumeration into combination enumeration. Passing i (not i + 1) allows reuse of the same element, which is the key difference from Combination Sum II.
• Always copy the current combination when adding to results. Passing the live reference means every entry in the result list points to the same object.
• Time complexity is O(2^target) in the worst case, but pruning keeps the actual exploration much smaller. The problem guarantees fewer than 150 valid combinations.
• This backtracking pattern transfers directly to permutations, subsets, N-Queens, and Sudoku. Invest time in understanding it thoroughly - it pays dividends across dozens of interview questions.

Related Problems

Once you're comfortable with Combination Sum, try these related backtracking problems:

• Combination Sum II - each element used at most once, input may have duplicates
• Subsets - generate all subsets of an array (backtracking without a target)
• Permutations - generate all orderings (no start index, use a visited set instead)
• Word Break - can a string be segmented using a dictionary (backtracking + memoization)

These are all available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed roles at top tech companies. The backtracking pattern you just learned is one of the most versatile tools in your interview toolkit. Build the muscle memory now, and these problems will feel routine when they show up on the whiteboard.

Solutions in Other Languages

JavaScript

class Solution {
  combinationSum(candidates, target) {
    const result = [];

    const backtrack = (remaining, start, path) => {
      if (remaining === 0) {
        result.push([...path]);
        return;
      }
      if (remaining < 0) {
        return;
      }

      for (let i = start; i < candidates.length; i++) {
        path.push(candidates[i]);
        backtrack(remaining - candidates[i], i, path);
        path.pop();
      }
    };

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

TypeScript

class Solution {
  combinationSum(candidates: number[], target: number): number[][] {
    const result: number[][] = [];

    const backtrack = (remaining: number, start: number, path: number[]): void => {
      if (remaining === 0) {
        result.push([...path]);
        return;
      }
      if (remaining < 0) {
        return;
      }

      for (let i = start; i < candidates.length; i++) {
        path.push(candidates[i]);
        backtrack(remaining - candidates[i], i, path);
        path.pop();
      }
    };

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

C++

#include <vector>

class Solution {
public:
  std::vector<std::vector<int>> combinationSum(std::vector<int> &candidates, int target) {
    std::vector<std::vector<int>> result;
    std::vector<int> combination;
    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 (candidates[i] <= target) {
        combination.push_back(candidates[i]);
        backtrack(candidates, target - candidates[i], i, combination, result);
        combination.pop_back();
      }
    }
  }
};

The C++ version integrates the pruning directly into the loop condition with if (candidates[i] <= target), skipping candidates that would overshoot the target. This avoids an extra recursive call just to hit the target < 0 base case.

Go

func CombinationSum(candidates []int, target int) [][]int {
    var result [][]int
    var combination []int

    var backtrack func(start, target int)
    backtrack = func(start, target int) {
        if target == 0 {
            combCopy := make([]int, len(combination))
            copy(combCopy, combination)
            result = append(result, combCopy)
            return
        }

        for i := start; i < len(candidates); i++ {
            if candidates[i] <= target {
                combination = append(combination, candidates[i])
                backtrack(i, target-candidates[i])
                combination = combination[:len(combination)-1]
            }
        }
    }

    backtrack(0, target)
    return result
}

Go requires explicit slice copying with make and copy since slices share underlying arrays. The combination[:len(combination)-1] reslice is Go's equivalent of pop().

Kotlin

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

    private fun backtrack(
        candidates: IntArray,
        target: Int,
        start: Int,
        current: MutableList<Int>,
        result: MutableList<List<Int>>
    ) {
        if (target == 0) {
            result.add(current.toList())
            return
        }
        if (target < 0) {
            return
        }

        for (i in start until candidates.size) {
            current.add(candidates[i])
            backtrack(candidates, target - candidates[i], i, current, result)
            current.removeAt(current.lastIndex)
        }
    }
}

Scala

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

    backtrack(target, 0, Nil, Nil)
  }
}

The Scala version uses immutable lists and foldLeft instead of mutation. Each recursive call prepends to the path and accumulates results functionally. No explicit backtracking step is needed since immutable data structures are never modified.

Swift

class Solution {
    func combinationSum(_ candidates: [Int], _ target: Int) -> [[Int]] {
        var result: [[Int]] = []
        var current: [Int] = []
        backtrack(candidates, 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
        }
        if target < 0 {
            return
        }

        for i in start..<candidates.count {
            current.append(candidates[i])
            backtrack(candidates, target - candidates[i], i, &current, &result)
            current.removeLast()
        }
    }
}

Rust

impl Solution {
    pub fn combination_sum(&self, candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        let mut result: Vec<Vec<i32>> = Vec::new();
        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;
        }
        if target < 0 {
            return;
        }

        for i in start..candidates.len() {
            current.push(candidates[i]);
            Self::backtrack(candidates, target - candidates[i], i, current, result);
            current.pop();
        }
    }
}

Ruby

class Solution
  def combination_sum(candidates, target)
    result = []
    backtrack(candidates, target, 0, [], result)
    result
  end

  def backtrack(candidates, target, start, current, result)
    if target == 0
      result << current.dup
      return
    end
    if target < 0
      return
    end

    (start...candidates.length).each do |i|
      current << candidates[i]
      backtrack(candidates, target - candidates[i], i, current, result)
      current.pop
    end
  end
end

C#

using System.Collections.Generic;

public class Solution {
    public List<List<int>> combinationSum(int[] candidates, int target) {
        var result = new List<List<int>>();
        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;
        }
        if (target < 0) {
            return;
        }

        for (int i = start; i < candidates.Length; i++) {
            current.Add(candidates[i]);
            Backtrack(candidates, target - candidates[i], i, current, result);
            current.RemoveAt(current.Count - 1);
        }
    }
}

Dart

class Solution {
  List<List<int>> combinationSum(List<int> candidates, int target) {
    List<List<int>> result = [];
    _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;
    }
    if (target < 0) {
      return;
    }

    for (int i = start; i < candidates.length; i++) {
      current.add(candidates[i]);
      _backtrack(candidates, target - candidates[i], i, current, result);
      current.removeLast();
    }
  }
}

PHP

class Solution {
    public function combinationSum(array $candidates, int $target): array {
        $result = [];
        $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;
        }
        if ($target < 0) {
            return;
        }

        for ($i = $start; $i < count($candidates); $i++) {
            $current[] = $candidates[$i];
            $this->backtrack($candidates, $target - $candidates[$i], $i, $current, $result);
            array_pop($current);
        }
    }
}

PHP passes arrays by value by default, so $current is automatically copied when passed to the recursive call. The $result array uses pass-by-reference (&$result) to accumulate results across calls.