Combination Sum

Mediumbacktrackingrecursion
Category: Backtracking
Companies that ask this question:
AmazonFacebookGoogleMicrosoft
LeetCode →NeetCode →

Approach

Combination Sum

Problem Statement

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

Examples

Example 1

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Explanation:
2 + 2 + 3 = 7
7 = 7

Example 2

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3

Input: candidates = [2], target = 1
Output: []

Intuition

We need combinations (not permutations), so [2,2,3] and [2,3,2] are the same.

Key difference from Subsets: We can reuse elements, and we have a target sum constraint.

Approach: Use backtracking with:

  • Pruning: Stop early if sum exceeds target
  • Reuse: Can pick same element multiple times
  • Order: Start from current index to avoid duplicates

Pattern Recognition

This is a Backtracking with Target problem:

  • Decision tree exploration
  • Early termination (pruning)
  • Element reuse allowed
  • Avoid permutations

Approach

Backtracking Solution

def backtrack(start, current, total):
  if total == target:
    result.append(current.copy())
    return
  if total > target:  # Pruning
    return

  for i in range(start, len(candidates)):
    current.append(candidates[i])
    # Can reuse same element: pass i (not i+1)
    backtrack(i, current, total + candidates[i])
    current.pop()

Key points:

  • Pass i (not i+1) to allow reuse
  • Prune when sum exceeds target
  • Start from start index to avoid duplicates

Optimization

Sort candidates first for better pruning:

  • If candidates[i] + total > target, all larger elements will also exceed
  • Can break early instead of continuing loop

Edge Cases

  • Target = 0 (return empty combination)
  • No valid combinations
  • Single element that divides target
  • Target smaller than smallest candidate

Complexity Analysis

  • Time: O(n^(t/m)) where:

    • n = candidates length
    • t = target
    • m = minimum candidate value
    • Worst case: exponential in target/min_value

  • Space: O(t/m) recursion depth

    • Maximum depth = target / minimum value

Solution

java
1import java.util.*;
2
3class Solution {
4    public List<List<Integer>> combinationSum(int[] candidates, int target) {
5        List<List<Integer>> result = new ArrayList<>();
6        backtrack(0, candidates, target, new ArrayList<>(), 0, result);
7        return result;
8    }
9
10    private void backtrack(int start, int[] candidates, int target,
11                          List<Integer> current, int total,
12                          List<List<Integer>> result) {
13        // Found valid combination
14        if (total == target) {
15            result.add(new ArrayList<>(current));
16            return;
17        }
18
19        // Prune: exceeded target
20        if (total > target) {
21            return;
22        }
23
24        // Try each candidate starting from 'start'
25        for (int i = start; i < candidates.length; i++) {
26            current.add(candidates[i]);
27            // Can reuse same element: pass i (not i+1)
28            backtrack(i, candidates, target, current, total + candidates[i], result);
29            current.remove(current.size() - 1);
30        }
31    }
32}
33
Loading visualizer...