DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Combination Sum | Backtracking

#algorithms #computerscience #interview #leetcode
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
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

Why?

Because the same element can be used multiple times.

Example:

candidates = [2,3,6,7]
target = 7
Enter fullscreen mode Exit fullscreen mode

To form:

[2,2,3]
Enter fullscreen mode Exit fullscreen mode

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);
    }
}
Enter fullscreen mode Exit fullscreen mode

Dry Run

Input 

candidates = [2,3,6,7]
target = 7
Enter fullscreen mode Exit fullscreen mode

Recursion Tree 

7

Pick 2
|
5

Pick 2
|
3

Pick 2
|
1 (Invalid)

Backtrack

Pick 3
|
0 ✅
Enter fullscreen mode Exit fullscreen mode

Combination:

[2,2,3]
Enter fullscreen mode Exit fullscreen mode

Another path:

Pick 7
|
0 ✅
Enter fullscreen mode Exit fullscreen mode

Combination:

[7]
Enter fullscreen mode Exit fullscreen mode

Output 

[
 [2,2,3],
 [7]
]
Enter fullscreen mode Exit fullscreen mode

Why Staying on Same Index Works?

When we pick:

candidates[index]
Enter fullscreen mode Exit fullscreen mode

we call:

helper(index, ...)
Enter fullscreen mode Exit fullscreen mode

instead of:

helper(index + 1, ...)
Enter fullscreen mode Exit fullscreen mode

This allows:

2 → 2 → 2
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Similar Problems

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

Top comments (0)