Combination Sum

Combination Sum looks like a math puzzle but it is really a backtracking question. You pick numbers that add up to a target, and here you may reuse the same number as many times as you like. The interesting part is how you allow reuse without producing the same combination in two different orders. That control is what is being tested.

🎯 The Problem

You get an array of distinct positive numbers and a target. You find every combination that sums to the target.

The rules:

• Each number may be used any number of times.
• Order inside a combination does not matter. So [2,2,3] and [3,2,2] are the same. Keep only one.
• The input numbers are all distinct and positive.
• Return every combination that adds up exactly to the target.

Input:  candidates = [2, 3, 6, 7], target = 7
Output: [[2,2,3], [7]]

Explanation: 2+2+3 = 7 and 7 = 7. Numbers may repeat.

Here is the problem as a running total that shrinks toward zero. Each pick lowers what is left to reach.

🐢 Approach 1: Try Every Subset of Picks (Brute Force)

The idea:

• List every multiset of numbers up to the target length.
• Add up each one.
• Keep the ones that sum to the target.

Why it is weak:

• You build endless number lists, most far past the target.
• You waste work on sums that already overshot.
• The same combination shows up in many orders. You then have to dedupe.
• It is exponential and very slow in practice.

Here is the brute-force recursive code for that idea:

def combination_sum(candidates, target):
    result = []

    def dfs(path, total):
        if total == target:
            result.append(path[:])
            return
        if total > target:
            return
        for num in candidates:
            dfs(path + [num], total + num)

    dfs([], 0)
    normalized = {tuple(sorted(path)) for path in result}
    return [list(path) for path in sorted(normalized)]

⚡ Approach 2: Backtracking With Reuse (Best)

The idea in one line: build the combination one pick at a time, allow the same number again, and never go backward.

How backtracking works here:

• Backtracking means choose a number, recurse deeper, then undo the choice.
• The path is the numbers picked so far.
• We track how much of the target is still left.

How reuse works:

• After picking a number, you may pick it again.
• So on recursion you pass the same index, not the next one.
• That lets one number repeat many times in a row.

How it avoids duplicates:

• Each call only picks from the current index onward. Never backward.
• This forces every combination into non-decreasing order.
• So each combination is built exactly one way.

How a branch stops:

• Remaining target is exactly zero. Record the combination.
• Remaining target drops below zero. Overshoot. Stop the branch.

Why it is fast:

• It only walks valid paths, not every random ordering.
• Sorting first lets you cut a branch the moment a number is larger than what is left. Optional but nice.

The picture below dry-runs the target 7 case. Passing the same index lets 2 repeat, while never going backward keeps the order fixed.

Steps to Solve

1. Create a result list and a path for the current combination.
2. Start a recursive helper with the full target and a start index of 0.
3. If the remaining target is 0, record a copy of the path and return.
4. If the remaining target is below 0, return without recording.
5. Loop over candidates from the start index to the end.
6. Add the current number to the path. This is the choose step.
7. Recurse with the same index, so the number can be reused, and the target reduced.
8. Remove the number you just added. This is the un-choose step.

#include <stdio.h>

int cand[] = {2, 3, 6, 7};
int n = 4;
int path[20];

void printCombo(int len) {
    printf("[");
    for (int i = 0; i < len; i++) {
        printf("%d", path[i]);
        if (i < len - 1) printf(",");
    }
    printf("]\n");
}

void backtrack(int start, int remain, int len) {
    if (remain == 0) { printCombo(len); return; }  // exact match
    if (remain < 0) return;                         // overshoot
    for (int i = start; i < n; i++) {
        path[len] = cand[i];                        // choose
        backtrack(i, remain - cand[i], len + 1);    // same i = reuse allowed
        // overwrite next loop = un-choose
    }
}

int main(void) {
    backtrack(0, 7, 0);
    return 0;
}

[2,2,3]
[7]

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> result;
vector<int> path;

void backtrack(vector<int>& cand, int start, int remain) {
    if (remain == 0) { result.push_back(path); return; }  // exact match
    if (remain < 0) return;                                // overshoot
    for (int i = start; i < (int)cand.size(); i++) {
        path.push_back(cand[i]);                           // choose
        backtrack(cand, i, remain - cand[i]);              // same i = reuse
        path.pop_back();                                   // un-choose
    }
}

int main() {
    vector<int> cand = {2, 3, 6, 7};
    backtrack(cand, 0, 7);
    for (auto& c : result) {
        cout << "[";
        for (int i = 0; i < (int)c.size(); i++) {
            cout << c[i];
            if (i < (int)c.size() - 1) cout << ",";
        }
        cout << "]" << endl;
    }
    return 0;
}

[2,2,3]
[7]

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

public class CombinationSum {
    static List<List<Integer>> result = new ArrayList<>();
    static List<Integer> path = new ArrayList<>();

    static void backtrack(int[] cand, int start, int remain) {
        if (remain == 0) { result.add(new ArrayList<>(path)); return; } // exact
        if (remain < 0) return;                                          // overshoot
        for (int i = start; i < cand.length; i++) {
            path.add(cand[i]);                                           // choose
            backtrack(cand, i, remain - cand[i]);                        // same i = reuse
            path.remove(path.size() - 1);                                // un-choose
        }
    }

    public static void main(String[] args) {
        int[] cand = {2, 3, 6, 7};
        backtrack(cand, 0, 7);
        System.out.println(result);
    }
}

[[2, 2, 3], [7]]

def combination_sum(candidates, target):
    result = []
    path = []

    def backtrack(start, remain):
        if remain == 0:                 # exact match found
            result.append(path[:])
            return
        if remain < 0:                  # overshot the target
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])              # choose
            backtrack(i, remain - candidates[i])    # same i = reuse allowed
            path.pop()                              # un-choose

    backtrack(0, target)
    return result


print(combination_sum([2, 3, 6, 7], 7))

[[2, 2, 3], [7]]

function combinationSum(candidates, target) {
  const result = [];
  const path = [];

  function backtrack(start, remain) {
    if (remain === 0) {                 // exact match found
      result.push([...path]);
      return;
    }
    if (remain < 0) return;             // overshot the target
    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);                 // choose
      backtrack(i, remain - candidates[i]);     // same i = reuse allowed
      path.pop();                               // un-choose
    }
  }

  backtrack(0, target);
  return result;
}

console.log(JSON.stringify(combinationSum([2, 3, 6, 7], 7)));

[[2,2,3],[7]]

Let us walk through the Python version line by line, because the reuse and the stop rules are the heart of it.

if remain == 0 checks whether the picked numbers add up exactly to the target. When they do, we record a copy of the path and return. The path[:] copy is needed so later changes do not corrupt this stored combination.

if remain < 0 checks for overshoot. If the remaining target dropped below zero, the last pick was too big, so we stop this branch.

for i in range(start, len(candidates)) loops over candidates from the start index onward. We never look before start. This is what keeps combinations in non-decreasing order, so no two combinations are just reorderings of each other.

path.append(candidates[i]) is the choose step.

backtrack(i, remain - candidates[i]) is the explore step, and it is the special line. We pass i, not i + 1. Passing the same index means the very same number can be picked again on the next level. That is how reuse works. We also subtract the number from the remaining target.

path.pop() is the un-choose step. After the branch returns, we remove the number we added, so the next loop turn starts clean.

⏱️ Time and Space Complexity

Because numbers can repeat, the recursion tree can grow deep. In the worst case the time is exponential, roughly O(2^t) where t relates to how many times the smallest number fits into the target. The exact bound depends on the candidates. The extra space is O(target divided by the smallest number) for the recursion depth, which is the longest a path can get.

🧩 Key Takeaways

• ✅ You may reuse each number as many times as needed to reach the target.
• ✅ Pass the same index on recursion to allow reuse of the current number.
• ✅ Never go backward, so combinations stay in one order and do not repeat.
• ✅ Stop a branch when the remaining target is exactly 0 (record) or below 0 (overshoot).
• ✅ The un-choose step pops the last number so the next sibling starts clean.

🚀 What’s Next?

• Combination Sum II
• Subsets