Problem Statement

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

A number may be chosen unlimited times.

Brute Force Intuition

For every element, we have two choices:

Pick it
Skip it

If we pick an element, we can pick it again because repetitions are allowed.

We keep exploring all possible combinations until:

• Target becomes 0 → Valid combination
• Target becomes negative → Invalid path

Pattern Recognition

Whenever you see:

• Generate all possible combinations
• Target Sum
• Unlimited usage of elements

Think:

Backtracking + Pick / Not Pick

Key Observation

Unlike Subsets:

After picking an element,
we stay at the same index.

Why?

Because the same element can be used multiple times.

Example:

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

To form:

[2,2,3]

we must be able to pick 2 repeatedly.

Optimal Java Solution

import java.util.*;

class Solution {

 public List<List<Integer>> combinationSum(int[] candidates, int target) {

 List<List<Integer>> ans = new ArrayList<>();

 helper(0, candidates, target, ans, new ArrayList<>());

 return ans;
 }

 private void helper(int index,
 int[] candidates,
 int target,
 List<List<Integer>> ans,
 List<Integer> ds) {

 if (target == 0) {
 ans.add(new ArrayList<>(ds));
 return;
 }

 if (index == candidates.length) {
 return;
 }

 // Pick
 if (candidates[index] <= target) {

 ds.add(candidates[index]);

 helper(index,
 candidates,
 target - candidates[index],
 ans,
 ds);

 ds.remove(ds.size() - 1);
 }

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

Dry Run

Input

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

Recursion Tree

7

Pick 2
|
5

Pick 2
|
3

Pick 2
|
1 (Invalid)

Backtrack

Pick 3
|
0 ✅

Combination:

[2,2,3]

Another path:

Pick 7
|
0 ✅

Combination:

[7]

Output

[
 [2,2,3],
 [7]
]

Why Staying on Same Index Works?

When we pick:

candidates[index]

we call:

helper(index, ...)

instead of:

helper(index + 1, ...)

This allows:

2 → 2 → 2

or any number of repeated selections.

Without this, each number could be used only once.

Complexity Analysis

Where:

T = Target

Recursion depth can grow up to target in worst case.

Interview One-Liner

Use backtracking with Pick / Not Pick. When picking an element, stay at the same index because elements can be reused multiple times.

Pattern Learned

Target Sum
+
Generate All Combinations
+
Unlimited Usage Allowed

=> Backtracking
=> Pick / Not Pick
=> Stay on Same Index After Pick

Similar Problems

• Combination Sum
• Coin Change (Generate Ways)
• Unbounded Knapsack
• Rod Cutting
• Integer Break