Combination Sum Algorithm Solutions and Implementation Guide

The combination sum problem involves finding all unique combinations of numbers that sum to a target value, with various constraints on element usage and repetition. This guide presents multiple solution approaches with detailed complexity analysis.

1. Pattern Restatement

Clarifying questions to ask the interviewer:

1. Are duplicates allowed in the input array? If so, do we allow using the same number multiple times in a combination?
2. What is the expected return format - should we return all combinations or just count them?
3. Can we modify the input array, or must we work with a copy?
4. What is the maximum size of the input array and target value?
5. Should we optimize for time or space complexity in follow-ups?

Restate the pattern or problem type in your own words: This is a classic backtracking/recursive combination generation problem where we need to find all unique combinations of numbers from a given array that sum up to a target value. Each number in the array can be used multiple times, and combinations are considered unique based on the count of each number used.

Clarify the signal words and constraint shape that point to it:

• "Find all combinations" or "generate all valid sets"
• "Sum to target" or "reach a specific value"
• "Use elements multiple times" (indicates repetition allowed)
• "Unique combinations" (suggests backtracking approach to avoid duplicates)
• Input array with positive integers (typical for combination sum problems)

Note any assumptions you are making:

• Input array contains only positive integers (common in combination sum problems)
• We're looking for unique combinations, not permutations
• The target value is a positive integer
• We can reuse numbers from the input array (each number has unlimited availability)

Identify whether the pattern is best suited for static, streaming, or online scenarios: This pattern is primarily designed for static input scenarios where all elements are known upfront. It's not naturally suited for streaming data since we need to explore all possible combinations from a complete set of candidates. The problem is well-suited for batch processing where we can analyze the entire input space at once.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "Find all combinations" or "return all valid solutions"
• "Sum equals target" or "total equals desired value"
• "Given a set of numbers" or "array of candidates"
• "Can use elements multiple times" or "repetition allowed"
• "Return combinations in any order"

Why this pattern fits better than the most common alternatives: This pattern is distinct from basic two-sum or subset problems because it requires generating all valid combinations rather than just finding one solution. Unlike permutation problems that focus on ordering, combination sum focuses on value accumulation with repetition allowed. The key difference from standard subset problems is that we're looking for combinations that sum to a target, not just any subset.

Conditions where a variation or related pattern applies instead:

• If the problem asks for exactly one combination (use greedy or two-pointer approach)
• If elements can only be used once (use standard backtracking without repetition)
• If we need to find combinations with specific count constraints (use constrained backtracking)
• If the target is not a sum but a product or other operation (use different mathematical approach)

The core insight that makes this pattern work: The fundamental insight is that we can build combinations incrementally by choosing elements from the candidate set and recursively exploring all valid paths. Since repetition is allowed, we don't need to track which elements have been used in the current path. The key optimization is to sort candidates and use early termination when remaining sum becomes negative, avoiding unnecessary recursive calls. This creates a tree search where each branch represents adding a specific element to the current combination.

This pattern is particularly efficient when we can sort the input and prune branches early, making it ideal for problems where we need to enumerate all valid solutions rather than just determining their existence.

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach with nested loops because we need to find all combinations that sum to target, but that would be O(n^k) where k is the number of combinations, which is exponential. That's not efficient at all.

Let me think about how to optimize this. I notice that if I sort the array first, I can use backtracking with pruning to avoid redundant computations. The key insight is that once I fix a number at a position, I don't need to consider numbers smaller than it in subsequent recursive calls - this prevents duplicate combinations.

If I maintain the invariant that each recursive call only considers elements at or after the current index, I can ensure combinations are generated in sorted order and avoid duplicates. This reduces it to O(2^n) worst case but with much better practical performance due to pruning.

I'm also thinking about using a dynamic programming approach, but that's more suited for counting combinations rather than generating them. The backtracking with pruning is better here because we need the actual combinations, not just their count.

Let me think about what happens when I have duplicate numbers in the input array. If I sort first and skip duplicates at each level, I can avoid generating identical combinations.

Brute-force approach and why it is not ideal:

The brute force approach would involve generating all possible subsets and checking if their sum equals target. For an array of size n, there are 2^n subsets, and checking each subset takes O(n) time in worst case. This gives us O(n × 2^n) complexity, which is exponential and becomes intractable even for moderate input sizes.

Improved approach and the key optimization:

The key optimization is to use backtracking with pruning. By sorting the array first and maintaining a constraint that we only consider elements at or after the current index in recursive calls, we avoid generating duplicate combinations. Additionally, we can prune branches early when the current sum exceeds target.

Final approach with step-by-step reasoning:

1. Sort the input array to enable efficient pruning and avoid duplicates
2. Use recursive backtracking starting from index 0
3. At each step, try adding each remaining element to current combination
4. If current sum exceeds target, prune that branch (early termination)
5. If current sum equals target, add combination to result
6. For duplicate handling: skip elements that are same as previous element at same recursion level

Important invariants that must hold:

1. Array is sorted to enable pruning and duplicate elimination
2. Recursive calls only consider elements at or after current index to prevent duplicates
3. Current sum never exceeds target (pruning invariant)
4. Combination list is maintained in sorted order to ensure uniqueness

4. Data Structure Choice

For the Combination Sum problem, I'll use a recursive backtracking approach with the following key data structures:

Primary Data Structures

1. List of Lists (List<List<Integer>>) - to store all valid combinations

   • Used to collect and return all possible combinations that sum to the target
   • Each inner list represents one valid combination

2. Temporary List (List<Integer>) - for building current combination

   • Used during backtracking to maintain the current path of selected numbers
   • Gets added to result when target sum is achieved, then cleared for next path

3. Integer array (int[]) - input candidates

   • Used to iterate through available numbers for combinations
   • Can be mutated during backtracking (we can sort it to enable pruning)

Why These Choices Work

The recursive backtracking approach naturally fits this pattern because:

• We need to explore all possible combinations systematically
• The temporary list allows us to build and backtrack efficiently without creating new objects at each step
• Using a single list for current combination and adding/removing elements during backtracking is more memory-efficient than creating new lists

Time and Space Impact

• Time Complexity: O(N^(T/M)) where N is candidates length, T is target value, M is minimum candidate value
• Space Complexity: O(T/M) for recursion stack depth + O(N^(T/M)) for storing results
• The temporary list grows up to target/M in depth, and we store all valid combinations

Helper Structures

• Sorted input array - sorting enables early termination when candidates exceed remaining target
• No additional helper structures needed beyond what's naturally part of the backtracking approach

This choice enables clean, readable code that efficiently explores all valid combinations while maintaining optimal space usage for the backtracking process.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to show how it works step-by-step.

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

Step 1: Start with empty combination and target = 7

• Current combination: []
• Remaining target: 7
• Start from index 0 (candidate 2)

Step 2: Try candidate 2

• Add 2 to combination: [2]
• Remaining target: 5
• Continue from index 0 (can reuse same candidate)

Step 3: Try candidate 2 again

• Add 2 to combination: [2,2]
• Remaining target: 3
• Continue from index 0

Step 4: Try candidate 2 again

• Add 2 to combination: [2,2,2]
• Remaining target: 1
• Cannot proceed (1 < 2), backtrack

Step 5: Backtrack, try candidate 3 instead

• Remove last 2: [2,2]
• Add 3: [2,2,3]
• Remaining target: 0
• Target reached! Add [2,2,3] to results

Step 6: Backtrack further and try candidate 3 at first position

• Remove 2: [2]
• Add 3: [2,3]
• Remaining target: 2
• Continue from index 1 (can reuse 3)

Step 7: Try candidate 3 again

• Add 3: [2,3,3]
• Remaining target: -1
• Cannot proceed, backtrack

Step 8: Backtrack to [2] and try candidate 6

• Remove 3: [2]
• Add 6: [2,6]
• Remaining target: 1
• Cannot proceed (1 < 6), backtrack

Step 9: Backtrack to initial state, try candidate 3 at first position

• Start with [3]
• Remaining target: 4
• Continue from index 1

Step 10: Try candidate 3 again

• Add 3: [3,3]
• Remaining target: 1
• Cannot proceed, backtrack

Step 11: Try candidate 6

• Add 6: [3,6]
• Remaining target: -2
• Cannot proceed, backtrack

Step 12: Try candidate 7 at first position

• Start with [7]
• Remaining target: 0
• Target reached! Add [7] to results

Final Result: [[2,2,3], [7]]

The key insight is that we explore all possible combinations by:

1. Starting with each candidate as the first element
2. For each position, trying all candidates from current index onwards (to allow reuse)
3. When remaining target becomes 0, we have a valid combination
4. When remaining target becomes negative, we backtrack and try other candidates

The algorithm terminates correctly because:

• We explore all combinations systematically
• We never reuse candidates from earlier indices (to avoid duplicates like [2,3] and [3,2])
• We backtrack when a path is invalid (negative remaining target)
• We collect valid combinations when remaining target reaches exactly 0

6. Java Solution

import java.util.*;

public class CombinationSum {
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> currentCombination = new ArrayList<>();
        
        // Sort candidates to enable early termination and better pruning
        Arrays.sort(candidates);
        
        backtrack(candidates, target, 0, currentCombination, result);
        return result;
    }
    
    private void backtrack(int[] candidates, int remainingTarget, 
                          int startIndex, List<Integer> currentCombination, 
                          List<List<Integer>> result) {
        
        // Base case: if remaining target is 0, we found a valid combination
        if (remainingTarget == 0) {
            result.add(new ArrayList<>(currentCombination));
            return;
        }
        
        // If remaining target is negative, this path is invalid
        if (remainingTarget < 0) {
            return;
        }
        
        // Try each candidate starting from startIndex
        for (int i = startIndex; i < candidates.length; i++) {
            // Pruning: if current candidate exceeds remaining target, 
            // no need to check further candidates (since array is sorted)
            if (candidates[i] > remainingTarget) {
                break;
            }
            
            // Include current candidate in combination
            currentCombination.add(candidates[i]);
            
            // Recursive call - allow reuse of same element (i, not i+1)
            backtrack(candidates, remainingTarget - candidates[i], 
                     i, currentCombination, result);
            
            // Backtrack: remove the last added element
            currentCombination.remove(currentCombination.size() - 1);
        }
    }
}

This solution uses backtracking with pruning to find all unique combinations that sum to the target value. The key insight is to sort the candidates first so we can terminate early when a candidate exceeds the remaining target, and to allow reuse of elements by passing index i instead of i+1 in the recursive call.

7. Complexity Analysis

Time Complexity: O(N^(T/M+1)) where N is the number of candidates, T is the target value, and M is the minimal candidate value.

The recurrence relation for the time complexity can be expressed as T(N, T) = N × T(N, T-M), which solves to O(N^(T/M+1)). In the worst case, we explore all possible combinations, leading to exponential growth.

Space Complexity: O(T/M) for the recursion stack depth.

The maximum recursion depth occurs when we use the smallest candidate repeatedly to reach the target. For example, if the smallest candidate is 1 and target is T, we'll have T recursive calls. The space complexity also includes the space needed to store the result combinations, but that's not counted in the primary analysis.

Why these bounds are correct:

1. The recursion tree has a branching factor of N (number of candidates) at each level
2. The depth is bounded by T/M since we're decrementing by the minimum candidate value
3. Each leaf node represents a valid combination, and we only store one path at a time in the recursion stack
4. The actual number of combinations is much smaller than the worst-case exponential bound, but that's the upper bound for analysis

Is this optimal?

Yes, this is near-optimal for the combination sum problem. Since we must generate all valid combinations, any algorithm that produces the same output will have at least exponential time complexity in the worst case. The backtracking approach is optimal because:

• It avoids generating duplicate combinations through careful state management
• It prunes branches early when the current sum exceeds the target
• The time complexity matches the theoretical lower bound for generating all combinations

The solution is optimal in terms of both time and space complexity relative to the problem's requirements.

8. Edge Cases & Pitkins

Empty and Minimal Inputs

• Empty candidates array: Should return empty result list (no combinations possible)
• Single element array: Handle case where one number can form target sum
• Target = 0: Should return empty combination (empty list) if no zeros in candidates

Duplicate Values and Repeated States

• Duplicate candidates: Handle arrays with repeated numbers like [2, 3, 6, 7, 2] where 2 appears twice
• Duplicate combinations: Ensure [2,2,3] and [2,3,2] are not both returned (use ordering to avoid this)
• Zero values: If candidates contain 0, infinite combinations could be possible (but problem typically excludes this)

Boundary Conditions

• Negative numbers: If candidates can be negative, the problem becomes more complex and may require additional constraints
• Very large targets: Integer overflow considerations if target is near MAX_VALUE
• Large candidate arrays: Performance impact from exponential combination growth

Common Implementation Mistakes

• Not maintaining sorted order: Without proper ordering, same combinations can be generated multiple times in different orders
• Incorrect base case handling: Missing the case where remaining target becomes negative or zero
• Reusing same index: When using backtracking, ensure proper index tracking to avoid generating duplicate combinations
• Memory allocation: Not considering that result list can grow exponentially with input size

// Example edge case handling:
// Input: candidates = [2,3,6,7], target = 0
// Expected: [] (empty list)
//
// Input: candidates = [2,3,6,7], target = 7
// Expected: [[7]] (single combination)
//
// Input: candidates = [2,3,6,7], target = 1
// Expected: [] (no valid combinations)

9. Alternative Approaches

There are several alternative approaches to solving the combination sum problem, each with different trade-offs:

1. Dynamic Programming Approach: Instead of generating combinations, we can use DP to build up solutions. For each target value, we maintain a list of all combinations that sum to that value. The recurrence relation is: dp[i] = dp[i] + [num] + dp[i-num] for each number that can contribute to sum i. This approach has better space complexity for counting combinations but is more complex to implement correctly and doesn't naturally handle the "at most k elements" constraint.

2. BFS/Queue-based Approach: We can use a breadth-first search with a queue storing partial combinations and remaining targets. Each queue element contains the current combination, remaining target, and start index to avoid duplicates. This is intuitive but has higher space complexity due to the queue overhead and doesn't offer significant performance improvements over DFS.

3. Mathematical Approach with Generating Functions: For counting combinations rather than listing them, we could use generating functions or inclusion-exclusion principles. This is overkill for the typical problem and doesn't provide practical benefits for the combination listing requirement.

4. Backtracking with Early Termination: An alternative DFS approach that sorts the candidates first and terminates early when remaining target becomes negative. This can prune some branches but doesn't fundamentally change the complexity class.

The chosen DFS + backtracking approach is preferred because it's intuitive, easy to understand and debug, maintains clean state tracking, and naturally handles the constraint requirements. The alternatives either add unnecessary complexity or don't provide meaningful performance improvements for typical use cases.

The key advantage of the chosen approach is that it's naturally recursive and builds combinations incrementally, making it easier to reason about correctness and edge cases.

10. Test Cases

import java.util.*;

public class CombinationSumTestCases {
    public static void main(String[] args) {
        // Test case 1: Basic example from problem description
        int[] candidates1 = {2, 3, 6, 7};
        int target1 = 7;
        // Expected: [[2,2,3], [7]]
        
        // Test case 2: Multiple combinations possible
        int[] candidates2 = {2, 3, 5};
        int target2 = 8;
        // Expected: [[2,2,2,2], [2,3,3], [3,5]]
        
        // Test case 3: Single candidate that divides target
        int[] candidates3 = {2};
        int target3 = 4;
        // Expected: [[2,2]]
        
        // Test case 4: No valid combinations
        int[] candidates4 = {2, 3, 5};
        int target4 = 1;
        // Expected: []
        
        // Test case 5: Empty candidates array
        int[] candidates5 = {};
        int target5 = 1;
        // Expected: []
        
        // Test case 6: Target equals one candidate
        int[] candidates6 = {2, 3, 5};
        int target6 = 5;
        // Expected: [[5]]
        
        // Test case 7: With duplicates in candidates (should allow reuse)
        int[] candidates7 = {2, 2, 3, 7};
        int target7 = 8;
        // Expected: [[2,2,2,2], [2,3,3], [7]]
        
        // Test case 8: Large target with many combinations
        int[] candidates8 = {2, 3, 6, 7};
        int target8 = 18;
        // Expected: Multiple combinations
        
        // Test case 9: Single element array with zero target
        int[] candidates9 = {1};
        int target9 = 0;
        // Expected: [[]] - empty combination
        
        // Test case 10: Negative numbers (if allowed)
        int[] candidates10 = {-2, 3, 5};
        int target10 = 8;
        // Expected: [[3,5], [-2,-2,-2,-2]]
    }
}

Representative Sample Cases:

1. Basic case: candidates = [2,3,6,7], target = 7 → [[2,2,3], [7]]
2. Multiple valid combinations: candidates = [2,3,5], target = 8 → [[2,2,2,2], [2,3,3], [3,5]]
3. Single valid combination: candidates = [2], target = 4 → [[2,2]]

Tricky Case:

• Duplicate candidates with reuse: candidates = [2,2,3,7], target = 8 → [[2,2,2,2], [2,3,3], [7]]
  • This tests that we correctly handle duplicate elements in candidates array
  • The same element can be reused multiple times

Boundary Case:

• Zero target: candidates = [1], target = 0 → [[]]
  • This tests the edge case where we need to return one empty combination when target is zero
  • Empty list should not be returned for zero target

These test cases cover the core functionality and edge conditions that any valid solution must handle correctly.

11. Final Summary

The core idea is to systematically explore all valid combinations that sum to the target by using backtracking with pruning to avoid redundant computations. This solution works efficiently by maintaining a running sum and exploring possibilities in a depth-first manner while avoiding duplicate combinations through careful index management. The approach is optimal for the combination sum problem as it guarantees finding all unique combinations without missing any valid solutions, with time complexity bounded by the number of valid combinations and space complexity determined by the recursion depth.