Problem statement
Find all unique combinations of distinct positive candidates that add up to target. You may reuse a candidate unlimited times. [2,2,3] and [3,2,2] describe the same combination, not two answers.
The LeetCode problem and supplied task share these bounds: 1–30 distinct candidates, values 2–40 and target 1–40. The answer may be in any order. Positivity matters: a zero-valued reusable candidate would never reduce the gap and could cause infinite recursion.
Constraints & requirements
- CONTRACT
- Verified shared bounds: 1–30 distinct candidates, each 2–40, target 1–40. Reuse values, not permutations of the same combination. Do not modify the input.
Examples 3 test cases
Example 1 Case 1
- Input
nums=[2,3,6,7]; target=7- Output
[[2,2,3],[7]]
The first combination reuses 2; the second uses 7 once.
Example 2 Case 2
- Input
nums=[2,3,5]; target=8- Output
[[2,2,2,2],[2,3,3],[3,5]]
Different candidate frequencies give different combinations.
Example 3 Case 3
- Input
nums=[2]; target=1- Output
[]
A positive value larger than the gap cannot be taken.
Hints Optional
01Hint 1
Carry an index and remaining target.
02Hint 2
Taking stays at the same index; skipping moves to index+1.
03Hint 3
Copy the path when remaining is zero, then undo each temporary choice.
How to think before coding
Define a call by index, remaining target and current path. Remaining==0 is success; exhausting candidates with a positive gap is failure. Taking subtracts this positive value but keeps the index to allow reuse. Skipping increases the index. After taking, remove only the appended value. These choices prevent both infinite zero-progress calls and order-only duplicates.
Brute force and the improvement
One brute-force idea tries every ordered sequence of candidate values until its sum reaches or exceeds target, then deduplicates successful sequences as sorted value lists. With D=floor(target/minCandidate), there can be exponentially many sequences of length at most D; a loose O(D·(N+1)^D) bound includes checking and copying them. The temporary sequence uses O(D) space, plus the deduplication set. Order is not part of the requested answer, so remove that wasted work: fix candidate order, reuse the current candidate on take, and retire it permanently on skip.
Intuition: decide when you are done with a candidate
Suppose the next candidate is 2 and the gap is 7. Taking 2 leaves a gap of 5. Since 2 is reusable, the next decision may still choose 2. Skipping 2 means “I am finished using this candidate”; move on permanently.
The state (index, remaining, path) separates those ideas. The index controls which candidates are still available. Remaining tells us how much is missing. Path records the chosen values so we can return actual combinations.
Keeping candidate indices nondecreasing stops [2,3] and [3,2] from being generated as separate answers. Numerical sorting is not necessary when input candidates are distinct and output order is arbitrary.
Algorithm
- Save a copy of path when remaining is zero.
- Stop when no candidates remain and the gap is still positive.
- If the current value fits, append it and recurse at the same index with a smaller gap.
- Remove that appended value after the child returns.
- Explore skipping the current value at index+1.
Java solution
The take branch reuses the same candidate index; the skip branch advances. Each temporary path addition is removed by its waiting caller after the child returns.
import java.util.*;
class Solution {
public static List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> result = new ArrayList<>(); // Distinct positive candidates are required.
chooseReusable(nums, 0, target, new ArrayList<>(), result);
return result; // Order of combinations is not part of this contract.
}
private static void chooseReusable(int[] nums, int index, int remaining,
List<Integer> path, List<List<Integer>> result) {
if (remaining == 0) { // Selected values exactly meet the target.
result.add(new ArrayList<>(path)); // Copy before the shared path is undone.
return;
}
if (index == nums.length) return; // No candidates left for a still-positive gap.
if (nums[index] <= remaining) { // Positive candidates cannot help after overshooting.
path.add(nums[index]); // Choose this value.
chooseReusable(nums, index, remaining - nums[index], path, result); // SAME index permits reuse.
path.remove(path.size() - 1); // Undo exactly this call's choice before skipping.
}
chooseReusable(nums, index + 1, remaining, path, result); // Stop using this candidate.
}
public static void main(String[] args) {
System.out.println(combinationSum(new int[]{2, 3, 6, 7}, 7)); // [[2, 2, 3], [7]]
}
}The default invocation returns [[2,2,3],[7]]. Saving path directly would not work: later undo operations modify that very same object. new ArrayList<>(path) creates an independent saved answer.
Recursion tree and dry run

Read the text transcript
Follow the Java, step by step
Example: nums = [2,3,6,7], target = 7
What to track: Each call owns index and remaining. All calls share path and result. The timeline includes a failed branch before the first answer; later sibling searches are explicitly summarized.
-
Enter the root
Java operationchooseReusable(nums, 0, target, new ArrayList<>(), result);Stateindex = 0; remaining = 7; path = []; result = []No value has been chosen. nums[0] is 2, so the first decision concerns 2.
-
Take 2, without retiring it
Java operationchooseReusable(nums, index, remaining - nums[index], path, result);Statechild: index = 0; remaining = 5; path = [2]path.add has just appended 2. The waiting root still owns remaining = 7. Keeping index = 0 permits another 2.
-
Take two more times
Java operationpath.add(nums[index]);Statesuccessive children: remaining = 3, path = [2,2]; then remaining = 1, path = [2,2,2]Each take subtracts 2. These are separate recursive calls, not assignments to the waiting parent’s remaining.
-
The remaining 1 cannot be filled
Java operationif (nums[index] <= remaining)Stateremaining = 1; 2, 3, 6 and 7 all fail the fit check; eventually index = 4Only skip calls are made here. Reaching index == nums.length returns without saving an answer.
-
Undo the third 2
Java operationpath.remove(path.size() - 1);Stateresumed parent: index = 0; remaining = 3; path = [2,2]The caller removes the value it appended. It resumes with its original remaining = 3, not the failed child’s 1.
-
Skip 2, then take 3
Java operationchooseReusable(nums, index + 1, remaining, path, result);Stateskip child: index = 1; remaining = 3; path = [2,2]. Its take child has remaining = 0 and path = [2,2,3]Skipping retires 2 on this branch. The candidate 3 fits exactly, so its take child reaches the success condition.
-
Save a snapshot
Java operationresult.add(new ArrayList<>(path));Stateresult = [[2,2,3]]; current path = [2,2,3]remaining == 0 is checked before candidate exhaustion. A new list preserves this answer after path changes.
-
Return to the call that chose 3
Java operationpath.remove(path.size() - 1);Stateremaining = 3; path = [2,2]; result still contains [2,2,3]Removing 3 does not remove the saved answer. The skip-3 continuation tries 6 and 7, which do not fit 3.
-
Resume earlier callers
Java operationpath.remove(path.size() - 1);Stateafter later sibling searches: path restores to [2], then []; the root still has remaining = 7Each waiting caller undoes only its own appended 2. The omitted siblings find no additional answer before the root skips 2.
-
Find the other answer
Java operationchooseReusable(nums, index + 1, remaining, path, result);Stateroot skip chain reaches index = 3, remaining = 7, path = []; taking 7 reaches remaining = 0The search tries and finishes the 3 and 6 branches before reaching 7. It saves [7], then restores the path and returns both answers.
Final result: [[2,2,3],[7]]. After the whole search, path is empty; saved answer copies remain.
This excerpt follows one successful path for candidates [2,3,6,7], target 7. The full search also explores failed branches and [7].
(index 0, gap 7, []) take 2 → (index 0, gap 5, [2]) take 2 → (index 0, gap 3, [2,2]) skip 2 → (index 1, gap 3, [2,2]) take 3 → (index 1, gap 0, [2,2,3]) → save copy return → remove 3 → [2,2] later return → remove 2 → [2] later return → remove 2 → []
The final empty path is not a lost answer: the result already holds its own copy. It is the restored state needed before trying another branch.
Why it works
At every state, path sums to original target minus remaining. Taking preserves that equation. Skipping removes no chosen values and simply restricts future candidates. Every legal combination has a unique sequence of candidate frequencies; choosing each candidate that many times and then skipping reaches it. Candidate order cannot reverse, so another permutation cannot duplicate it.
Complexity and alternative approaches
Let N be candidate count, T the target and m the smallest candidate. A path takes at most floor(T/m) values and skips at most N candidates. A loose binary-tree bound is O(2^(N+T/m)) search work, plus the total lengths of saved combinations. Auxiliary stack/path space is O(N+T/m), excluding output.
The more informative description is O(V + S), where V is visited states and S is the number of values copied into answers. This is not O(2^N), because candidates are reusable.
A loop-based backtracker can choose the next candidate from a start index and recurse using i again. DP can count combinations or decide reachability efficiently, but returning all combinations still has output-sized work. Counting alone is not this task.
Common mistakes
- Advancing to index+1 after taking forbids reuse and solves a different variant.
- Restarting from index 0 after every choice generates order-only duplicates.
- Not undoing path makes sibling branches inherit extra values.
- Accepting zero or negative reusable candidates invalidates this pruning and termination argument.