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
| Metric | Complexity |
|---|---|
| Time Complexity | O(2^T) (Exponential) |
| Space Complexity | O(T) |
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