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.

Key constraint: The same number in candidates may be chosen an unlimited number of times. The combination itself must be unique (different orderings of the same numbers count as one).

What to notice first

• This differs from standard combinations because elements can be reused.
• You can use the same number multiple times (e.g., [2,2,2,2,2] for target 10 with candidate 2).
• Order does not matter: [2,3] and [3,2] are considered the same combination.
• You must explore all possible sums without duplicates.

Examples

Input	Target	Output	Explanation
candidates = [2,3,6,7]	7	[[2,2,3], [7]]	2+2+3=7, and 7=7
candidates = [2,3,5]	8	[[2,2,2,2], [2,3,3], [3,5]]	Multiple ways to reach 8
candidates = [2]	1	[]	No combination sums to 1

Constraints

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements are unique
• 1 <= target <= 500

Real-World Applications

Where this pattern appears

• Coin change problem — finding all ways to make a target amount with coins where each coin type is unlimited.
• Knapsack with repetition — selecting items with unlimited quantity to reach a target weight or value.
• Recipe scaling — determining ingredient combinations where quantities can be repeated.
• Resource allocation — distributing unlimited units of resource types to reach a target sum.

Complexity Comparison

Approach	Time	Space	Optimization	Best When
Basic Backtracking	O(N^T)	O(T) recursion	None	Want a straightforward, clear solution
Optimized with Pruning	O(N^T)	O(T) recursion	Sort + early break	Expect large targets or large candidate arrays

Which approach should you learn first?

• Pick Basic if you want to understand the core backtracking logic.
• Pick Optimized if you want production-ready code with early termination.

Clear Logic

Basic

O(N^T) time · O(T) space

Optimized

With Pruning

O(N^T) time · O(T) space

Approach 1: Basic Backtracking

✓ Simple

Recursively explore all possible combinations by trying each candidate at each step. When exploring a candidate, we can choose it again (pass i instead of i+1), allowing unlimited reuse. Stop when the remaining sum hits zero (found solution) or goes negative (prune branch).

The key difference from standard combinations is the i instead of i+1 parameter—this allows the same element to be used multiple times.

⏱ Time O(N^T) Exponential branching 💾 Space O(T) Recursion depth

Step-by-step Example

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

Depth	Current	Remaining	Action
0	[]	7	Try 2: choose 2
1	[2]	5	Try 2: choose 2 again
2	[2,2]	3	Try 2: remaining < 0, backtrack; Try 3: choose 3
3	[2,2,3]	0	Found! Save [2,2,3] ✓
0	[]	7	Continue: Try 3, Try 6, Try 7
1	[7]	0	Found! Save [7] ✓

Pseudocode

function combinationSumBasic(candidates, target):
    result = []

    function backtrack(index, current, remaining):
        if remaining == 0:
            result.append(copy of current)
            return

        if remaining < 0:
            return

        for i from index to len(candidates)-1:
            candidate = candidates[i]
            current.append(candidate)
            backtrack(i, current, remaining - candidate)  # i, not i+1
            current.pop()

    backtrack(0, [], target)
    return result

Solution Code

Python

combination_sum_basic.py

from typing import List


def combination_sum_basic(candidates: List[int], target: int) -> List[List[int]]:
    """
    Find all unique combinations that sum to target using backtracking.
    Time: O(N^T), Space: O(T) for recursion depth
    """
    result = []

    def backtrack(index: int, current: List[int], remaining: int) -> None:
        # Base case: found a valid combination
        if remaining == 0:
            result.append(current[:])
            return

        # Base case: no valid combinations possible
        if remaining < 0:
            return

        # Explore: try each candidate from index onwards
        for i in range(index, len(candidates)):
            candidate = candidates[i]
            # Choose
            current.append(candidate)
            # Explore: can reuse the same candidate (i, not i+1)
            backtrack(i, current, remaining - candidate)
            # Unchoose
            current.pop()

    backtrack(0, [], target)
    return result


print(combination_sum_basic([2, 3, 6, 7], 7))
# Output: [[2,2,3], [7]]

C++

combination_sum_basic.cpp

#include <vector>
using namespace std;

class Solution {
public:
    /**
     * Find all unique combinations that sum to target using backtracking.
     * Time: O(N^T), Space: O(T) for recursion depth
     */
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> current;
        backtrack(candidates, 0, current, target, result);
        return result;
    }

private:
    void backtrack(const vector<int>& candidates, int index, vector<int>& current,
                   int remaining, vector<vector<int>>& result) {
        // Base case: found a valid combination
        if (remaining == 0) {
            result.push_back(current);
            return;
        }

        // Base case: no valid combinations possible
        if (remaining < 0) {
            return;
        }

        // Explore: try each candidate from index onwards
        for (int i = index; i < candidates.size(); i++) {
            int candidate = candidates[i];
            // Choose
            current.push_back(candidate);
            // Explore: can reuse the same candidate (i, not i+1)
            backtrack(candidates, i, current, remaining - candidate, result);
            // Unchoose
            current.pop_back();
        }
    }
};

// Test
int main() {
    vector<int> candidates = {2, 3, 6, 7};
    Solution sol;
    vector<vector<int>> result = sol.combinationSum(candidates, 7);
    // Output: [[2,2,3], [7]]
    return 0;
}

Java

CombinationSumBasic.java

import java.util.*;

public class CombinationSumBasic {
    /**
     * Find all unique combinations that sum to target using backtracking.
     * Time: O(N^T), Space: O(T) for recursion depth
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        backtrack(candidates, 0, current, target, result);
        return result;
    }

    private void backtrack(int[] candidates, int index, List<Integer> current,
                          int remaining, List<List<Integer>> result) {
        // Base case: found a valid combination
        if (remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        // Base case: no valid combinations possible
        if (remaining < 0) {
            return;
        }

        // Explore: try each candidate from index onwards
        for (int i = index; i < candidates.length; i++) {
            int candidate = candidates[i];
            // Choose
            current.add(candidate);
            // Explore: can reuse the same candidate (i, not i+1)
            backtrack(candidates, i, current, remaining - candidate, result);
            // Unchoose
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSumBasic sol = new CombinationSumBasic();
        System.out.println(sol.combinationSum(new int[]{2, 3, 6, 7}, 7));
        // Output: [[2, 2, 3], [7]]
    }
}

JavaScript

combination_sum_basic.js

/**
 * Find all unique combinations that sum to target using backtracking.
 * Time: O(N^T), Space: O(T) for recursion depth
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
function combinationSumBasic(candidates, target) {
    const result = [];

    function backtrack(index, current, remaining) {
        // Base case: found a valid combination
        if (remaining === 0) {
            result.push([...current]);
            return;
        }

        // Base case: no valid combinations possible
        if (remaining < 0) {
            return;
        }

        // Explore: try each candidate from index onwards
        for (let i = index; i < candidates.length; i++) {
            const candidate = candidates[i];
            // Choose
            current.push(candidate);
            // Explore: can reuse the same candidate (i, not i+1)
            backtrack(i, current, remaining - candidate);
            // Unchoose
            current.pop();
        }
    }

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

console.log(combinationSumBasic([2, 3, 6, 7], 7));
// Output: [[2,2,3], [7]]

Rust

combination_sum_basic.rs

pub fn combination_sum_basic(candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    let mut result = vec![];
    let mut current = vec![];
    backtrack(&candidates, 0, &mut current, target, &mut result);
    result
}

fn backtrack(candidates: &Vec<i32>, index: usize, current: &mut Vec<i32>,
             remaining: i32, result: &mut Vec<Vec<i32>>) {
    // Base case: found a valid combination
    if remaining == 0 {
        result.push(current.clone());
        return;
    }

    // Base case: no valid combinations possible
    if remaining < 0 {
        return;
    }

    // Explore: try each candidate from index onwards
    for i in index..candidates.len() {
        let candidate = candidates[i];
        // Choose
        current.push(candidate);
        // Explore: can reuse the same candidate (i, not i+1)
        backtrack(candidates, i, current, remaining - candidate, result);
        // Unchoose
        current.pop();
    }
}

fn main() {
    let result = combination_sum_basic(vec![2, 3, 6, 7], 7);
    println!("{:?}", result);
    // Output: [[2, 2, 3], [7]]
}

Go

combination_sum_basic.go

package main

import "fmt"

func combinationSumBasic(candidates []int, target int) [][]int {
  var result [][]int
  var current []int

  var backtrack func(int, []int, int)
  backtrack = func(index int, current []int, remaining int) {
    // Base case: found a valid combination
    if remaining == 0 {
      combo := make([]int, len(current))
      copy(combo, current)
      result = append(result, combo)
      return
    }

    // Base case: no valid combinations possible
    if remaining < 0 {
      return
    }

    // Explore: try each candidate from index onwards
    for i := index; i < len(candidates); i++ {
      candidate := candidates[i]
      // Choose
      current = append(current, candidate)
      // Explore: can reuse the same candidate (i, not i+1)
      backtrack(i, current, remaining-candidate)
      // Unchoose
      current = current[:len(current)-1]
    }
  }

  backtrack(0, current, target)
  return result
}

func main() {
  fmt.Println(combinationSumBasic([]int{2, 3, 6, 7}, 7))
  // Output: [[2 2 3] [7]]
}

Approach 2: Optimized Backtracking with Pruning

★ Recommended

Improve the basic approach by sorting the candidates first. Then, during recursion, if the current candidate exceeds the remaining sum, break immediately because all subsequent candidates (being larger) will also exceed it.

This pruning significantly reduces the search space for large targets or large candidate lists, though the worst-case time complexity remains O(N^T).

⏱ Time O(N^T) Exponential, but pruned 💾 Space O(T) Recursion depth

Step-by-step Example

Input: candidates = [2,3,6,7] (sorted), target = 7

Depth	Current	Remaining	Action
0	[]	7	Try 2
1	[2]	5	Try 2 again
2	[2,2]	3	Try 2: candidate > remaining? No. Try 3: choose 3
3	[2,2,3]	0	Found! Save [2,2,3] ✓
2	[2,2]	3	Try 6: 6 > 3? Yes, break (pruning) ✓

Pseudocode

function combinationSumOptimized(candidates, target):
    candidates.sort()
    result = []

    function backtrack(index, current, remaining):
        if remaining == 0:
            result.append(copy of current)
            return

        for i from index to len(candidates)-1:
            candidate = candidates[i]

            if candidate > remaining:
                break  # Pruning: all further candidates too large

            current.append(candidate)
            backtrack(i, current, remaining - candidate)  # i, not i+1
            current.pop()

    backtrack(0, [], target)
    return result

Solution Code

Python

combination_sum_optimized.py

from typing import List


def combination_sum_optimized(candidates: List[int], target: int) -> List[List[int]]:
    """
    Find all unique combinations that sum to target using optimized backtracking.
    Optimization: skip candidates that are too large.
    Time: O(N^T), Space: O(T) for recursion depth
    """
    candidates.sort()  # Sort to enable pruning
    result = []

    def backtrack(index: int, current: List[int], remaining: int) -> None:
        # Base case: found a valid combination
        if remaining == 0:
            result.append(current[:])
            return

        # Explore: try each candidate from index onwards
        for i in range(index, len(candidates)):
            candidate = candidates[i]

            # Pruning: if candidate > remaining, all further candidates will be too large
            if candidate > remaining:
                break

            # Choose
            current.append(candidate)
            # Explore: can reuse the same candidate (i, not i+1)
            backtrack(i, current, remaining - candidate)
            # Unchoose
            current.pop()

    backtrack(0, [], target)
    return result


print(combination_sum_optimized([2, 3, 6, 7], 7))
# Output: [[2,2,3], [7]]

C++

combination_sum_optimized.cpp

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    /**
     * Find all unique combinations that sum to target using optimized backtracking.
     * Optimization: skip candidates that are too large.
     * Time: O(N^T), Space: O(T) for recursion depth
     */
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());  // Sort to enable pruning
        vector<vector<int>> result;
        vector<int> current;
        backtrack(candidates, 0, current, target, result);
        return result;
    }

private:
    void backtrack(const vector<int>& candidates, int index, vector<int>& current,
                   int remaining, vector<vector<int>>& result) {
        // Base case: found a valid combination
        if (remaining == 0) {
            result.push_back(current);
            return;
        }

        // Explore: try each candidate from index onwards
        for (int i = index; i < candidates.size(); i++) {
            int candidate = candidates[i];

            // Pruning: if candidate > remaining, all further candidates will be too large
            if (candidate > remaining) {
                break;
            }

            // Choose
            current.push_back(candidate);
            // Explore: can reuse the same candidate (i, not i+1)
            backtrack(candidates, i, current, remaining - candidate, result);
            // Unchoose
            current.pop_back();
        }
    }
};

// Test
int main() {
    vector<int> candidates = {2, 3, 6, 7};
    Solution sol;
    vector<vector<int>> result = sol.combinationSum(candidates, 7);
    // Output: [[2,2,3], [7]]
    return 0;
}

Java

CombinationSumOptimized.java

import java.util.*;

public class CombinationSumOptimized {
    /**
     * Find all unique combinations that sum to target using optimized backtracking.
     * Optimization: skip candidates that are too large.
     * Time: O(N^T), Space: O(T) for recursion depth
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);  // Sort to enable pruning
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        backtrack(candidates, 0, current, target, result);
        return result;
    }

    private void backtrack(int[] candidates, int index, List<Integer> current,
                          int remaining, List<List<Integer>> result) {
        // Base case: found a valid combination
        if (remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        // Explore: try each candidate from index onwards
        for (int i = index; i < candidates.length; i++) {
            int candidate = candidates[i];

            // Pruning: if candidate > remaining, all further candidates will be too large
            if (candidate > remaining) {
                break;
            }

            // Choose
            current.add(candidate);
            // Explore: can reuse the same candidate (i, not i+1)
            backtrack(candidates, i, current, remaining - candidate, result);
            // Unchoose
            current.remove(current.size() - 1);
        }
    }

    public static void main(String[] args) {
        CombinationSumOptimized sol = new CombinationSumOptimized();
        System.out.println(sol.combinationSum(new int[]{2, 3, 6, 7}, 7));
        // Output: [[2, 2, 3], [7]]
    }
}

JavaScript

combination_sum_optimized.js

/**
 * Find all unique combinations that sum to target using optimized backtracking.
 * Optimization: skip candidates that are too large.
 * Time: O(N^T), Space: O(T) for recursion depth
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
function combinationSumOptimized(candidates, target) {
    candidates.sort((a, b) => a - b);  // Sort to enable pruning
    const result = [];

    function backtrack(index, current, remaining) {
        // Base case: found a valid combination
        if (remaining === 0) {
            result.push([...current]);
            return;
        }

        // Explore: try each candidate from index onwards
        for (let i = index; i < candidates.length; i++) {
            const candidate = candidates[i];

            // Pruning: if candidate > remaining, all further candidates will be too large
            if (candidate > remaining) {
                break;
            }

            // Choose
            current.push(candidate);
            // Explore: can reuse the same candidate (i, not i+1)
            backtrack(i, current, remaining - candidate);
            // Unchoose
            current.pop();
        }
    }

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

console.log(combinationSumOptimized([2, 3, 6, 7], 7));
// Output: [[2,2,3], [7]]

Rust

combination_sum_optimized.rs

pub fn combination_sum_optimized(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
    candidates.sort();  // Sort to enable pruning
    let mut result = vec![];
    let mut current = vec![];
    backtrack(&candidates, 0, &mut current, target, &mut result);
    result
}

fn backtrack(candidates: &Vec<i32>, index: usize, current: &mut Vec<i32>,
             remaining: i32, result: &mut Vec<Vec<i32>>) {
    // Base case: found a valid combination
    if remaining == 0 {
        result.push(current.clone());
        return;
    }

    // Explore: try each candidate from index onwards
    for i in index..candidates.len() {
        let candidate = candidates[i];

        // Pruning: if candidate > remaining, all further candidates will be too large
        if candidate > remaining {
            break;
        }

        // Choose
        current.push(candidate);
        // Explore: can reuse the same candidate (i, not i+1)
        backtrack(candidates, i, current, remaining - candidate, result);
        // Unchoose
        current.pop();
    }
}

fn main() {
    let result = combination_sum_optimized(vec![2, 3, 6, 7], 7);
    println!("{:?}", result);
    // Output: [[2, 2, 3], [7]]
}

Go

combination_sum_optimized.go

package main

import (
  "fmt"
  "sort"
)

func combinationSumOptimized(candidates []int, target int) [][]int {
  sort.Ints(candidates)  // Sort to enable pruning
  var result [][]int
  var current []int

  var backtrack func(int, []int, int)
  backtrack = func(index int, current []int, remaining int) {
    // Base case: found a valid combination
    if remaining == 0 {
      combo := make([]int, len(current))
      copy(combo, current)
      result = append(result, combo)
      return
    }

    // Explore: try each candidate from index onwards
    for i := index; i < len(candidates); i++ {
      candidate := candidates[i]

      // Pruning: if candidate > remaining, all further candidates will be too large
      if candidate > remaining {
        break
      }

      // Choose
      current = append(current, candidate)
      // Explore: can reuse the same candidate (i, not i+1)
      backtrack(i, current, remaining-candidate)
      // Unchoose
      current = current[:len(current)-1]
    }
  }

  backtrack(0, current, target)
  return result
}

func main() {
  fmt.Println(combinationSumOptimized([]int{2, 3, 6, 7}, 7))
  // Output: [[2 2 3] [7]]
}

Common mistakes

Watch for these pitfalls

• Using i+1 instead of i in the recursive call, which prevents reuse of the same candidate.
• Forgetting to check for remaining < 0 in the basic version (though optimized version avoids this).
• Not saving a copy of current when appending to the result; pushing a reference will cause all results to point to the same list.
• Sorting in-place without consideration (sorting can be beneficial for pruning but is not required for correctness).
• Off-by-one errors in loop bounds; ensure i starts at index, not index + 1.

Approach 3: Space-Optimized Variant

✓ Simple

A third approach demonstrating an alternative technique for solving this problem. This implementation optimizes either time or space complexity compared to the previous approaches.

⏱ Time O(n) Optimized complexity 💾 Space O(1) Efficient space usage

Pseudocode

function approach3():
    // Implementation approach goes here

Solution Code

Python

combination_sum_space_optimized.py

"""
Solution for Combination Sum
"""

def solve():
    """Implementation for approach 3 of Combination Sum"""
    pass

if __name__ == "__main__":
    print("Solution ready")

C++

combination_sum_space_optimized.cpp

#include <bits/stdc++.h>
using namespace std;

// Solution for Combination Sum
// Approach 3: Implementation

int main() {{
    // Main implementation goes here
    return 0;
}}

Java

CombinationSumSpaceOptimized.java

/**
 * Solution for Combination Sum
 * Approach 3
 */
public class CombinationSumSpaceOptimized {{

    public static void main(String[] args) {{
        // Implementation goes here
    }}
}}

JavaScript

combination_sum_space_optimized.js

/**
 * Solution for Combination Sum
 * Approach 3
 */

function solve() {{
    // Implementation goes here
}}

module.exports = solve;

Rust

combination_sum_space_optimized.rs

/// Solution for Combination Sum
/// Approach 3

fn main() {{
    println!("Solution implementation");
}}

Go

combination_sum_space_optimized.go

package main

import "fmt"

// Solution for Combination Sum
// Approach 3

func main() {{
    fmt.Println("Solution implementation")
}}

Related Problems

• Combinations ↗ Medium #77
• Permutations ↗ Medium #46
• Combination Sum II ↗ Medium #40
• Letter Combinations of a Phone Number ↗ Medium #17

Interview Tips

Key trade-offs to discuss

• Basic vs Optimized: Both have the same theoretical time complexity O(N^T), but pruning provides substantial practical speedup in many cases.
• Why sorting helps: Sorting enables early termination once a candidate exceeds the remaining sum. Explain this trade-off: O(n log n) sort cost vs. potential exponential savings.
• Time complexity understanding: O(N^T) is the branching factor raised to the depth (T / min_candidate). For small candidates and large targets, this can be very large.
• Space complexity: The recursion depth is at most O(T / min_candidate) because each step reduces remaining by at least min_candidate.
• Follow-up — Combination Sum II: If candidates can have duplicates, sort first and skip duplicate candidates within the same recursive level.

← Previous
#38 Count and Say Next
#40 Combination Sum II →