L8. Combination Sum | Recursion | Leetcode | C++ | Java

Master the classic Combination Sum problem using recursion and backtracking. This chapter covers the foundational mental model of the Pick and Non-Pick framework, handles elements that can be chosen an unlimited number of times, walks through complete execution trees, analyzes time and space complexity, and provides production-ready implementations in both C++ and Java.

1. Problem Statement and Status Quo

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 the target. You may return the combinations in any order.

• Key Constraint: The same element can be chosen from the array an unlimited number of times.
• Goal: Find all valid subsets whose sum equals the target value.

Example Walkthrough

• Candidates: [2, 3, 6, 7]
• Target: 7
• Valid Output Combinations:
  • [2, 2, 3] ($2 + 2 + 3 = 7$)
  • [7] ($7 = 7$)

2. Core Mental Model: The Pick and Non-Pick Framework

Whenever a problem requires generating subsets or combinations from an array, the standard mental model to employ is the Pick and Non-Pick recursive paradigm.

• For every index in our candidate array, we face a binary branching decision:
  1. Pick the element: Include the element at the current index in our temporary data structure, reduce our target sum by that element's value, and stay at the same index (since elements can be picked multiple times).
  2. Do Not Pick the element: Skip the current index entirely, leave the target sum unchanged, and move forward to the next index.

Real-Life Analogy: Exploring Branching Choices

Think of standing at a fork in a maze where every junction offers two paths: Take the item into your backpack or Leave it and walk past. Because items can be duplicated, taking an item allows you to stand at that exact same junction again to see if you need another copy of it. If you choose to leave it behind, you permanently lock yourself out of that item and move down the hallway to the next option.

3. Step-by-Step Recursive Evolution

Let us trace how the recursion tree evolves using our candidate array [2, 3, 6, 7] and target 7.

The State Parameters

Our recursive function needs to track:

1. index: The current position in the candidates array.
2. target: The remaining sum we need to fulfill.
3. ds: A temporary data structure (list/vector) storing the current combination.
4. ans: The final container storing all valid combinations.

Branching Mechanics

4. Complete Flow Walkthrough: Tracing Example [2, 3], Target 5

Let us trace a smaller execution path to see how the combination [2, 3] is successfully formed for target 5:

1. Start at index = 0, target = 5, ds = [].
   • Pick 2: ds = [2], target becomes $5 - 2 = 3$. Stay at index = 0.
     • Pick 2: ds = [2, 2], target becomes $3 - 2 = 1$. Stay at index = 0.
       • Pick 2: Candidate 2 > target 1. Cannot pick.
       • Not Pick 2: Move to index = 1 (value 3). Target = 1.
         • Pick 3: Candidate 3 > target 1. Cannot pick.
         • Not Pick 3: Move to index = 2 (Out of bounds). Stop.
     • Backtrack: Remove last 2, ds = [2], target = 3.
     • Not Pick 2: Move to index = 1 (value 3). Target = 3.
       • Pick 3: ds = [2, 3], target becomes $3 - 3 = 0$.
         • Target == 0 REACHED! Add [2, 3] to final answer list. Return.

5. Real-World Practical Pitfalls & Backtracking Safeguards

When writing recursive algorithms that modify a shared data structure (ds), you must remember to backtrack correctly.

• The Pitfall: After a recursive call returns, the element you added to your temporary list (ds) is still sitting in that list. If you do not remove it before exploring the "Not Pick" branch, your combinations will be polluted with unwanted elements from previous branches.
• The Fix: Always clean up your state immediately after the recursive call finishes executing:
  JAVA

  Copy

  // Java Backtracking Cleanup
  ds.add(candidates[index]);
  findCombinations(index, target - candidates[index], candidates, ans, ds);
  ds.remove(ds.size() - 1); // <-- BACKTRACKING STEP
  

6. Complexity Analysis

Understanding the time and space complexity of exponential recursion problems is crucial for interviews.

7. Java Implementation

Below is the clean, production-grade Java solution implementing the Pick and Non-Pick backtracking pattern.

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

public class CombinationSum {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        findCombinations(0, target, candidates, ans, new ArrayList<>());
        return ans;
    }

    private void findCombinations(int index, int target, int[] candidates, List<List<Integer>> ans, List<Integer> ds) {
        // Base Case: If we reach the end of the candidates array
        if (index == candidates.length) {
            if (target == 0) {
                ans.add(new ArrayList<>(ds));
            }
            return;
        }

        // Pick Condition: Element must be less than or equal to target
        if (candidates[index] <= target) {
            ds.add(candidates[index]);
            // Stay at the same index because elements can be reused
            findCombinations(index, target - candidates[index], candidates, ans, ds);
            // Backtrack: Remove the element to explore other paths
            ds.remove(ds.size() - 1);
        }

        // Not Pick Condition: Move to the next index without picking current element
        findCombinations(index + 1, target, candidates, ans, ds);
    }
}

8. C++ Implementation

Below is the equivalent high-performance C++ solution using std::vector for memory management and backtracking.

#include <vector>

class Solution {
private:
    void findCombinations(int index, int target, std::vector<int>& candidates, std::vector<std::vector<int>>& ans, std::vector<int>& ds) {
        // Base Case: Reached the end of candidates array
        if (index == candidates.size()) {
            if (target == 0) {
                ans.push_back(ds);
            }
            return;
        }

        // Pick Condition
        if (candidates[index] <= target) {
            ds.push_back(candidates[index]);
            // Stay at the same index for unlimited reuse
            findCombinations(index, target - candidates[index], candidates, ans, ds);
            // Backtrack
            ds.pop_back();
        }

        // Not Pick Condition
        findCombinations(index + 1, target, candidates, ans, ds);
    }

public:
    std::vector<std::vector<int>> combinationSum(std::vector<int>& candidates, int target) {
        std::vector<std::vector<int>> ans;
        std::vector<int> ds;
        findCombinations(0, target, candidates, ans, ds);
        return ans;
    }
};

Summary and Key Takeaways

• Problem Nature: Combination Sum requires generating all subsets that sum to a specific target value using backtracking.
• The Pick / Not-Pick Paradigm: Every recursive step evaluates whether to include the current candidate or skip it entirely.
• Element Reuse: By passing the same index during the "Pick" recursive call, we allow elements to be selected an unlimited number of times.
• Index Progression: By passing index + 1 during the "Not Pick" call, we guarantee forward movement and prevent infinite loops across distinct candidate choices.
• Backtracking Integrity: Always remember to remove elements from your temporary data structure (ds.remove() in Java, ds.pop_back() in C++) immediately after a recursive branch returns.
• Base Case Termination: Recursion terminates either when the index exceeds array bounds or when the target sum is successfully exhausted (target == 0).
• Time Complexity Dynamics: Bounded primarily by $O(2^t)$ where $t$ represents the target value scaled by minimum candidate weights.