Introduction

If you are preparing for coding interviews or improving your Data Structures and Algorithms skills, LeetCode 39 Combination Sum is one of the most important backtracking problems to learn. This problem helps you understand how recursion explores multiple possibilities and how combinations are generated efficiently. It is a foundational problem that builds strong problem-solving skills and prepares you for many advanced recursion and backtracking questions.

Why Should You Solve This Problem?

Combination Sum is not just another coding question — it teaches you how to think recursively and break a complex problem into smaller decisions. By solving it, you learn how to manage recursive paths, avoid duplicate combinations, and build interview-level backtracking intuition. Once you understand this pattern, problems like subsets, permutations, N-Queens, and Sudoku Solver become much easier to approach.

LeetCode Problem Link

Problem Name: Combination Sum

Problem Link: Combination Sum

Problem Statement

Given an array of distinct integers called candidates and a target integer target, you need to return all unique combinations where the chosen numbers sum to the target.

Important rules:

1. You can use the same number unlimited times.
2. Only unique combinations should be returned.
3. Order of combinations does not matter.

Example

Example 1

Input:

Output:

Explanation

1. 2 + 2 + 3 = 7
2. 7 itself equals target

Understanding the Problem in Simple Words

We are given some numbers.

We need to:

1. Pick numbers from the array
2. Add them together
3. Reach the target sum
4. Use numbers multiple times if needed
5. Avoid duplicate combinations

This problem belongs to the Backtracking + Recursion category.

Real-Life Analogy

Imagine you have coins of different values.

You want to make an exact payment.

You can reuse coins multiple times.

You need to find every possible valid coin combination.

This is exactly what Combination Sum does.

Intuition Behind the Solution

At every index, we have two choices:

1. Pick the current number
2. Skip the current number

Since numbers can be reused unlimited times, when we pick a number, we stay at the same index.

This creates a recursion tree.

We continue until:

1. Target becomes 0 → valid answer
2. Target becomes negative → invalid path
3. Array ends → stop recursion

Why Backtracking Works Here

Backtracking helps us:

1. Explore all possible combinations
2. Undo previous decisions
3. Try another path

It is useful whenever we need:

1. All combinations
2. All subsets
3. Path exploration
4. Recursive searching

Approach 1: Backtracking Using Pick and Skip

Core Idea

At every element:

1. Either take it
2. Or move to next element

Java Code (Pick and Skip Method)

Approach 2: Backtracking Using Loop (Optimized)

This is the cleaner and more optimized version.

Your code belongs to this category.

Java Code (Loop-Based Backtracking)

Dry Run of the Algorithm

Input

Step-by-Step Execution

Start:

Pick 2

Pick 2 again:

Pick 2 again:

No valid choice possible.

Backtrack.

Try 3

Valid answer found.

Add:

Try 7

Valid answer found.

Add:

Final Output

Recursion Tree Visualization

Every branch explores a different combination.

Time Complexity Analysis

Time Complexity

More accurately:

Where:

1. N = Number of candidates
2. Target = Required sum

Reason:

Every number can be picked multiple times.

This creates many recursive branches.

Space Complexity

Reason:

Recursion stack stores elements.

Maximum recursion depth depends on target.

Why We Pass Same Index Again

Notice this line:

We pass i, not i+1.

Why?

Because we can reuse the same number unlimited times.

If we used i+1, we would move forward and lose repetition.

Why Duplicate Combinations Are Not Created

We start loop from current index.

This guarantees:

and

are not both generated.

Order remains controlled.

Common Mistakes Beginners Make

1. Using i+1 Instead of i

Wrong:

This prevents reuse.

2. Forgetting Backtracking Step

Wrong:

Without removing, recursion keeps incorrect values.

3. Missing Target == 0 Base Case

This is where valid answer is stored.

Important Interview Insight

Combination Sum is a foundational problem.

It helps build understanding for:

1. Combination Sum II
2. Subsets
3. Permutations
4. N-Queens
5. Word Search
6. Sudoku Solver

This question is frequently asked in coding interviews.

Pattern Recognition

Use Backtracking when problem says:

1. Find all combinations
2. Generate all subsets
3. Find all paths
4. Use recursion
5. Explore possibilities

Optimized Thinking Strategy

Whenever you see:

1. Target sum
2. Repeated selection
3. Multiple combinations

Think:

Edge Cases

Case 1

Output:

No possible answer.

Case 2

Output:

Interview Answer in One Line

“We use backtracking to recursively try all candidate numbers while reducing the target and backtrack whenever a path becomes invalid.”

Final Java Code

Key Takeaways

1. Combination Sum uses Backtracking.
2. Reuse same element by passing same index.
3. Target becomes smaller in recursion.
4. Backtracking removes last element.
5. Very important for interview preparation.

Frequently Asked Questions

Is Combination Sum DP or Backtracking?

It is primarily solved using Backtracking.

Dynamic Programming can also solve it but recursion is more common.

Why is this Medium difficulty?

Because:

1. Requires recursion understanding
2. Requires backtracking logic
3. Requires duplicate prevention

Can we sort the array?

Yes.

Sorting can help with pruning.

Conclusion

LeetCode 39 Combination Sum is one of the best problems to learn recursion and backtracking.

Once you understand this pattern, many interview problems become easier.

The loop-based recursive solution is clean, optimized, and interview-friendly.

If you master this question, you gain strong understanding of recursive decision trees and combination generation.