Blind 75Medium

Combination Sum — Backtracking with Reuse

Perform depth-first search, deciding how many times to pick each candidate while keeping the combination in non-decreasing order.

BacktrackingDFS

View problem on LeetCode

Problem Statement

Given candidates with positive integers and a target, return all unique combinations where candidates can be picked unlimited times to reach the target.

Why This Problem Matters

Illustrates how backtracking manages search space pruning with bounding conditions.
Emphasises ordering to avoid duplicate combinations without extra sets.
Teaches you to push/pop list state cleanly—an essential interview skill.

Thought Process

Sort the input for determinism

Sorting helps prune branches early when the running sum exceeds the target and keeps combinations ordered.

Use DFS with current index

At each recursive step, decide whether to include the current candidate again or move to the next one.

Terminate on exact sums

When remaining target hits zero, copy the path into the answer list; when it goes negative, backtrack immediately.

Step-by-Step Reasoning

Sort candidates to guarantee non-decreasing combinations.
Call dfs(startIndex, remainingTarget, path).
Loop i from startIndex to candidates.length - 1; skip branches where candidates[i] > remainingTarget.
Push candidates[i], recurse with i (allow reuse), then pop to backtrack.

Dry Run

candidates = [2,3,6,7], target = 7

Path [2,2,3] and [7] collected after exploring reuse and advance branches.

remaining < 0

Branch pruned immediately to keep recursion tree small.

Complexity Analysis

Time

O(N·T)

Space

O(T)

Why

Worst-case exponential in target/Tmin but bounded by recursion depth equal to target divided by smallest candidate.

Annotated Solution

JAVA

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class CombinationSum {
  public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> results = new ArrayList<>();
    backtrack(candidates, target, 0, new ArrayList<>(), results);
    return results;
  }

  private void backtrack(int[] candidates, int remaining, int start, List<Integer> path, List<List<Integer>> results) {
    if (remaining == 0) {
      results.add(new ArrayList<>(path));
      return;
    }

    for (int i = start; i < candidates.length; i += 1) {
      int value = candidates[i];
      if (value > remaining) {
        break;
      }

      path.add(value);
      backtrack(candidates, remaining - value, i, path, results);
      path.remove(path.size() - 1);
    }
  }
}

Sorting allows early pruning. Passing i during recursion lets the same candidate be used multiple times without re-sorting combinations.

Common Pitfalls

Not sorting leads to duplicate combinations appearing in different orders.
Forgetting to pop after the recursive call corrupts later paths.
Allowing the loop to continue after remainingTarget < 0 wastes time exploring impossible branches.

Follow-Up Questions

How do you change the logic when each candidate can only be used once? (Advance index i + 1 on recursion.)
How would you prevent duplicates when the input contains repeated numbers? (Skip equal numbers after sorting.)

Key Takeaways

Backtracking problems hinge on disciplined push/pop logic.

Ordering your exploration often removes the need for auxiliary deduplication structures.

Stopping early when the remaining target dips below zero keeps the recursion tree tractable.