Combination Sum

Problem Description

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

Constraints

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

Branching Decisions: Reuse or Move On

If we simply loop over all elements at each recursion step, we will generate duplicate combinations. For example, with candidates = [2, 3] and target = 5, we would find both [2, 3] and [3, 2].

To avoid duplicates, we enforce a strict index ordering during backtracking. At any node in our decision tree, we have two options:

1. Include the current candidate at index i in our combination and keep the pointer at i (allowing it to be reused in the next step).
2. Exclude the current candidate and increment the index to i + 1 (preventing it from being chosen again).

This creates a binary decision tree where every leaf is evaluated exactly once, eliminating duplicate combinations without needing expensive post-traversal set deduplications.

Solution 1: Decision Tree Backtracking

Recursively traverse the decision tree, adding numbers to the current path and backtracking when constraints are met.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        dfs(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void dfs(int[] candidates, int target, int i, List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current)); // found a valid combination
            return;
        }
        if (i >= candidates.length || target < 0) {
            return; // out of bounds or exceeded target sum
        }

        // Decision 1: include candidates[i] and continue searching (can reuse)
        current.add(candidates[i]);
        dfs(candidates, target - candidates[i], i, current, result);
        current.remove(current.size() - 1); // backtrack

        // Decision 2: skip candidates[i] and move to the next candidate
        dfs(candidates, target, i + 1, current, result);
    }
}

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

        def dfs(i, current, total):
            if total == target:
                result.append(list(current))  # found a valid combination
                return
            if i >= len(candidates) or total > target:
                return  # out of bounds or exceeded target sum

            # Decision 1: include candidates[i] (can reuse)
            current.append(candidates[i])
            dfs(i, current, total + candidates[i])
            current.pop()  # backtrack

            # Decision 2: skip candidates[i] and move to next
            dfs(i + 1, current, total)

        dfs(0, [], 0)
        return result

#include <vector>

class Solution {
private:
    void dfs(const std::vector<int>& candidates, int target, int i, 
             std::vector<int>& current, std::vector<std::vector<int>>& result) {
        if (target == 0) {
            result.push_back(current); // found a valid combination
            return;
        }
        if (i >= candidates.size() || target < 0) {
            return; // out of bounds or exceeded target sum
        }

        // Decision 1: include candidates[i] (can reuse)
        current.push_back(candidates[i]);
        dfs(candidates, target - candidates[i], i, current, result);
        current.pop_back(); // backtrack

        // Decision 2: skip candidates[i] and move to next
        dfs(candidates, target, i + 1, current, result);
    }

public:
    std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        dfs(candidates, target, 0, current, result);
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(2^T) where T is the target value. The decision tree has a branching factor of 2 at each level, and the maximum depth of the tree is target / min_candidate.
• Space Complexity: O(T / min_candidate) representing the maximum recursion stack depth.

Where it breaks: If candidates contain values like 1 and the target is large, the recursion stack depth grows linearly with the target. In this problem, candidate values are at least 2, bounding the stack height.

Common Mistakes

• Forgetting to copy the current combination list before adding it to the result. If you add the list reference directly (e.g. result.add(current)), subsequent backtracking mutations will modify the output values, yielding empty lists.
• Allowing infinite recursion by not checking target < 0. If you omit the negative target base case check, the search will continue indefinitely.
• Generating duplicate combinations by not restricting search indexing. Re-scanning all candidates from index 0 on every call generates permutations instead of combinations.

Frequently Asked Questions

Can we sort the candidates to optimize the search? Yes. If you sort the candidates array first, you can break the loop early if candidates[i] > target, saving unnecessary recursive calls.

How does this differ from Permutations? Permutations (LeetCode 46) require ordering (e.g., [1, 2] is different from [2, 1]) and each number can only be used once. This problem requires unique combinations and allows unlimited reuse of numbers.

What does this problem test in interviews? It tests your ability to model decision processes as a binary tree, implement backtracking recursions, and avoid duplicate combinations.

← All Problems