LeetCode 39: Combination Sum — Java Backtracking Solution

Preparing for coding interviews and facing challenges with combination problems? One common and powerful example is LeetCode Problem 39: Combination Sum. It’s a classic that tests your understanding of backtracking—a must-know technique in problem-solving.

In this guide, we’ll walk through the problem statement, explain the backtracking approach, share a well-structured Java solution, and break down the time and space complexity.

🧩 Problem Overview

You’re given an array of distinct integers candidates and a target integer target. Your task is to return all unique combinations in which the numbers sum up to target. You can use each number unlimited times.

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

Each combination should be in non-decreasing order, and the same set of numbers in a different order should not be counted as a unique combination.

🔍 Why Backtracking?

Backtracking is ideal for exploring all possible combinations efficiently. Here’s why this method works so well:

• Controlled Exploration: We explore each candidate starting from a given index to avoid permutations of the same combination (like [2,3,2] vs [3,2,2]).
• Recursive Depth Search: Subtracting the chosen number from the remaining target allows deep exploration of valid paths.
• Early Pruning: If the remaining target goes negative, we stop exploring that path.

💡 Java Backtracking Solution

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<>();
        backtrack(0, candidates, target, new ArrayList<>(), result);
        return result;
    }

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

        for (int i = start; i < candidates.length; i++) {
            current.add(candidates[i]);
            backtrack(i, candidates, remaining - candidates[i], current, result);
            current.remove(current.size() - 1);
        }
    }
}

🧠 Code Walkthrough

Let’s break down the logic behind the implementation:

1. Main Method:
   • Initializes a results list.
   • Calls the recursive backtrack method starting at index 0.
2. Backtrack Method Parameters:
   • start: Keeps track of the index to begin from (prevents duplicate permutations).
   • remaining: Remaining value to reach the target.
   • current: Current combination being built.
   • result: List of all valid combinations.
3. Key Conditions:
   • If remaining == 0: We found a valid combination, so add a copy of current to the result.
   • If remaining < 0: Stop exploring that path.
4. Recursive Exploration:
   • Try each candidate starting from start.
   • Recurse after choosing a candidate.
   • Remove the last added number (backtrack) to explore the next option.

📊 Time & Space Complexity

• Time Complexity: O(2^N) in the worst case. Each candidate can either be included or excluded, and recursion explores all such paths.
• Space Complexity: O(T/M), where T is the target and M is the smallest candidate value. This reflects the recursion depth.

📝 Key Takeaways

• Backtracking is a must-know strategy for solving combinatorial problems efficiently.
• Non-decreasing combinations ensure uniqueness and eliminate redundant permutations.
• Recursive tree pruning (when the sum exceeds the target) significantly improves performance.

🙋 Frequently Asked Questions

Q1: Why not use dynamic programming here?
Backtracking explicitly lists all valid combinations. DP is better suited for counting results, not generating them.

Q2: How does the algorithm avoid duplicate combinations?
By iterating from the current index (start), the algorithm ensures combinations are generated in a consistent, non-decreasing order.

Q3: What if candidates contains duplicate numbers?
This approach assumes all elements in candidates are distinct. For duplicates, you’d need to sort the array and skip repeated elements to avoid redundant results.

🧪 Practice Next

Want to level up? Try these related problems:

1. Combination Sum II (LeetCode 40) – Candidates may include duplicates.
2. Subsets (LeetCode 78) – Generate all possible subsets.
3. Permutations (LeetCode 46) – Explore every possible ordering.

🚀 Final Thoughts

The Combination Sum problem is a great introduction to backtracking and recursive problem-solving. Mastering it gives you a solid foundation to tackle more complex algorithmic challenges in interviews and real-world applications.

Try the code, tweak it, and explore different edge cases. With practice, you’ll build the intuition needed to ace problems like this effortlessly.

Let me know if you’d like a downloadable version or diagrams to visualize the recursion tree!