AlgoViz
HomeRecursion

Combination Sum

Medium

Reuse allowed, so stay on the same index

Problem

Given distinct candidates and a target, return all unique combinations that sum to target; each number may be reused unlimited times.

In simple words

Try each candidate, allowing reuse; recurse on the smaller remaining target and backtrack.

The idea

At each step either use the current candidate again — recursing on the same index with a reduced target — or move past it permanently. Never moving backwards is what stops the same combination appearing in a different order.

The trick

  • Recurse on the same index when taking, so unlimited reuse is allowed.
  • Prune the branch as soon as the target goes negative.
  • Moving only forward gives uniqueness without a deduplication pass.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

2
3
6
7
0
1
2
3

Step 1 of 2. Here's the example — candidates=[2,3,6,7], target=7 Values: 2, 3, 6, 7.

1/2
Optimal
timeO(2^t)spaceO(t)
1f(i, target, cur):2  if target==0: output cur; return3  if i==n or target<0: return4  cur.push(c[i]); f(i, target-c[i], cur); cur.pop()   // reuse i5  f(i+1, target, cur)                                   // skip i

Input

array
[2, 3, 6, 7]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
candidates = [2, 3, 6, 7], target = 7
Output:
[[2, 2, 3], [7]]
Explanation:
2+2+3 and 7 both make 7.

Example 2

Input:
candidates = [2, 3, 5], target = 8
Output:
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]
Explanation:
Three ways reach 8.

Example 3

Input:
candidates = [2], target = 1
Output:
[]
Explanation:
Can't make 1 from 2 → none.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.