Combination Sum

Given an array of distinct integers and a target, return all unique combinations where the chosen numbers sum to target (elements may be reused)

Language Selection

Choose your preferred programming language

Showing: Python

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.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Constraints:

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

Examples:

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.

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: []
Explanation: No combination sums to 1.

Approach 1: Backtracking (Basic)

Algorithm:

  1. Sort candidates (optional but helps with reasoning about order)
  2. Use a recursive function starting from index 0
  3. At each step, try adding the current candidate (can reuse, so do not advance the index)
  4. Also try skipping the current candidate (advance the index)
  5. When the remaining target reaches 0, record the combination
  6. If the remaining target goes negative or we run out of candidates, backtrack

Time Complexity: O(n^(T/M)) where T is target and M is the minimum candidate Space Complexity: O(T/M) for the recursion depth

Python:

def combinationSum(candidates, target):
    """
    Find all unique combinations summing to target using backtracking
    Time: O(n^(T/M))
    Space: O(T/M) recursion depth
    """
    result = []

    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return

        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                continue
            current.append(candidates[i])
            # Pass i (not i+1) because we can reuse the same element
            backtrack(i, current, remaining - candidates[i])
            current.pop()  # Backtrack

    backtrack(0, [], target)
    return result

Java:

class Solution {
    /**
     * Find all unique combinations summing to target using backtracking
     * Time: O(n^(T/M))
     * Space: O(T/M) recursion depth
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, 0, new ArrayList<>(), target, result);
        return result;
    }

    private void backtrack(int[] candidates, int start, List<Integer> current,
                           int remaining, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) {
                continue;
            }
            current.add(candidates[i]);
            // Pass i (not i+1) because we can reuse the same element
            backtrack(candidates, i, current, remaining - candidates[i], result);
            current.remove(current.size() - 1);  // Backtrack
        }
    }
}

Go:

// combinationSum - Find all unique combinations summing to target using backtracking
// Time: O(n^(T/M))
// Space: O(T/M) recursion depth
func combinationSum(candidates []int, target int) [][]int {
    var result [][]int

    var backtrack func(start int, current []int, remaining int)
    backtrack = func(start int, current []int, remaining int) {
        if remaining == 0 {
            combo := make([]int, len(current))
            copy(combo, current)
            result = append(result, combo)
            return
        }

        for i := start; i < len(candidates); i++ {
            if candidates[i] > remaining {
                continue
            }
            current = append(current, candidates[i])
            // Pass i (not i+1) because we can reuse the same element
            backtrack(i, current, remaining-candidates[i])
            current = current[:len(current)-1] // Backtrack
        }
    }

    backtrack(0, []int{}, target)
    return result
}

JavaScript:

/**
 * Find all unique combinations summing to target using backtracking
 * Time: O(n^(T/M))
 * Space: O(T/M) recursion depth
 */
function combinationSum(candidates, target) {
    const result = [];

    function backtrack(start, current, remaining) {
        if (remaining === 0) {
            result.push([...current]);
            return;
        }

        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) {
                continue;
            }
            current.push(candidates[i]);
            // Pass i (not i+1) because we can reuse the same element
            backtrack(i, current, remaining - candidates[i]);
            current.pop();  // Backtrack
        }
    }

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

C#:

public class Solution {
    /// <summary>
    /// Find all unique combinations summing to target using backtracking
    /// Time: O(n^(T/M))
    /// Space: O(T/M) recursion depth
    /// </summary>
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        IList<IList<int>> result = new List<IList<int>>();
        Backtrack(candidates, 0, new List<int>(), target, result);
        return result;
    }

    private void Backtrack(int[] candidates, int start, List<int> current,
                           int remaining, IList<IList<int>> result) {
        if (remaining == 0) {
            result.Add(new List<int>(current));
            return;
        }

        for (int i = start; i < candidates.Length; i++) {
            if (candidates[i] > remaining) {
                continue;
            }
            current.Add(candidates[i]);
            // Pass i (not i+1) because we can reuse the same element
            Backtrack(candidates, i, current, remaining - candidates[i], result);
            current.RemoveAt(current.Count - 1);  // Backtrack
        }
    }
}

Approach 2: Backtracking with Sorting and Pruning

Algorithm:

  1. Sort the candidates array in ascending order
  2. Use backtracking starting from index 0
  3. Since the array is sorted, once a candidate exceeds the remaining target, all subsequent candidates will also exceed it
  4. Break out of the loop early instead of continuing, pruning entire subtrees

Time Complexity: O(n^(T/M)) where T is target and M is the minimum candidate Space Complexity: O(T/M) for the recursion depth

Python:

def combinationSum(candidates, target):
    """
    Find all unique combinations with sorting and pruning
    Time: O(n^(T/M))
    Space: O(T/M) recursion depth
    """
    candidates.sort()  # Sort to enable pruning
    result = []

    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(current[:])
            return

        for i in range(start, len(candidates)):
            # Pruning: if current candidate exceeds remaining, all subsequent will too
            if candidates[i] > remaining:
                break
            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])
            current.pop()  # Backtrack

    backtrack(0, [], target)
    return result

Java:

class Solution {
    /**
     * Find all unique combinations with sorting and pruning
     * Time: O(n^(T/M))
     * Space: O(T/M) recursion depth
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);  // Sort to enable pruning
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, 0, new ArrayList<>(), target, result);
        return result;
    }

    private void backtrack(int[] candidates, int start, List<Integer> current,
                           int remaining, List<List<Integer>> result) {
        if (remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            // Pruning: if current candidate exceeds remaining, all subsequent will too
            if (candidates[i] > remaining) {
                break;
            }
            current.add(candidates[i]);
            backtrack(candidates, i, current, remaining - candidates[i], result);
            current.remove(current.size() - 1);  // Backtrack
        }
    }
}

Go:

// combinationSum - Find all unique combinations with sorting and pruning
// Time: O(n^(T/M))
// Space: O(T/M) recursion depth
func combinationSum(candidates []int, target int) [][]int {
    sort.Ints(candidates) // Sort to enable pruning
    var result [][]int

    var backtrack func(start int, current []int, remaining int)
    backtrack = func(start int, current []int, remaining int) {
        if remaining == 0 {
            combo := make([]int, len(current))
            copy(combo, current)
            result = append(result, combo)
            return
        }

        for i := start; i < len(candidates); i++ {
            // Pruning: if current candidate exceeds remaining, all subsequent will too
            if candidates[i] > remaining {
                break
            }
            current = append(current, candidates[i])
            backtrack(i, current, remaining-candidates[i])
            current = current[:len(current)-1] // Backtrack
        }
    }

    backtrack(0, []int{}, target)
    return result
}

JavaScript:

/**
 * Find all unique combinations with sorting and pruning
 * Time: O(n^(T/M))
 * Space: O(T/M) recursion depth
 */
function combinationSum(candidates, target) {
    candidates.sort((a, b) => a - b);  // Sort to enable pruning
    const result = [];

    function backtrack(start, current, remaining) {
        if (remaining === 0) {
            result.push([...current]);
            return;
        }

        for (let i = start; i < candidates.length; i++) {
            // Pruning: if current candidate exceeds remaining, all subsequent will too
            if (candidates[i] > remaining) {
                break;
            }
            current.push(candidates[i]);
            backtrack(i, current, remaining - candidates[i]);
            current.pop();  // Backtrack
        }
    }

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

C#:

public class Solution {
    /// <summary>
    /// Find all unique combinations with sorting and pruning
    /// Time: O(n^(T/M))
    /// Space: O(T/M) recursion depth
    /// </summary>
    public IList<IList<int>> CombinationSum(int[] candidates, int target) {
        Array.Sort(candidates);  // Sort to enable pruning
        IList<IList<int>> result = new List<IList<int>>();
        Backtrack(candidates, 0, new List<int>(), target, result);
        return result;
    }

    private void Backtrack(int[] candidates, int start, List<int> current,
                           int remaining, IList<IList<int>> result) {
        if (remaining == 0) {
            result.Add(new List<int>(current));
            return;
        }

        for (int i = start; i < candidates.Length; i++) {
            // Pruning: if current candidate exceeds remaining, all subsequent will too
            if (candidates[i] > remaining) {
                break;
            }
            current.Add(candidates[i]);
            Backtrack(candidates, i, current, remaining - candidates[i], result);
            current.RemoveAt(current.Count - 1);  // Backtrack
        }
    }
}

Key Insights

  1. Reuse Allowed: Unlike standard combination problems, the same element can be used multiple times. This is achieved by passing i (not i + 1) to the recursive call.

  2. Start Index Prevents Duplicates: By only considering candidates from index start onward, we avoid generating duplicate combinations like [2,3] and [3,2].

  3. Sorting Enables Pruning: When candidates are sorted, once a candidate exceeds the remaining target, all subsequent candidates are guaranteed to exceed it too. Using break instead of continue prunes entire subtrees.

  4. Recursion Depth: The maximum recursion depth is target / min(candidates), since in the deepest branch we repeatedly use the smallest candidate.

  5. Exponential Nature: The problem is inherently exponential because the number of valid combinations can grow exponentially with the target value.

Edge Cases

  • No valid combination: candidates = [2], target = 1 returns []
  • Single candidate equals target: candidates = [7], target = 7 returns [[7]]
  • Single candidate used multiple times: candidates = [2], target = 4 returns [[2,2]]
  • Target is 1 with all candidates greater than 1: returns []
  • Large target with small candidates: produces many combinations, pruning is critical for performance

Test Cases

# Test case 1: Multiple combinations
result = combinationSum([2,3,6,7], 7)
assert sorted([sorted(c) for c in result]) == sorted([[2,2,3],[7]])

# Test case 2: Repeated use of elements
result = combinationSum([2,3,5], 8)
assert sorted([sorted(c) for c in result]) == sorted([[2,2,2,2],[2,3,3],[3,5]])

# Test case 3: No valid combination
assert combinationSum([2], 1) == []

# Test case 4: Single element equals target
result = combinationSum([7], 7)
assert result == [[7]]

# Test case 5: All candidates usable
result = combinationSum([1,2], 3)
assert sorted([sorted(c) for c in result]) == sorted([[1,1,1],[1,2]])

Common Mistakes

  1. Using i + 1 instead of i: Advancing the index prevents reuse of the same element. For this problem, we must pass i to allow unlimited reuse.
  2. Using continue instead of break after sorting: When the array is sorted and a candidate exceeds the remaining target, continue wastes time checking larger candidates. Use break for effective pruning.
  3. Forgetting to copy the current list: Appending a reference instead of a copy causes all result entries to be empty after backtracking completes.
  4. Not using a start index: Without the start index, the algorithm generates permutations of the same combination (e.g., both [2,3] and [3,2]), resulting in duplicates.
  5. Negative remaining without guard: Without checking candidates[i] > remaining, the recursion can go deep with negative remaining values before terminating, wasting time.