External Publication

Combination Sum | Backtracking

DEV Community [Unofficial] June 17, 2026

leetcode.com

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