Problem statement

Given an array of distinct positive integers candidates and a target, return all unique combinations where the chosen numbers sum to target. A number may be used unlimited times.

Output order: each combination in non-decreasing order; combinations listed in lexicographic order.

Example 1

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

Example 2

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3

Input: candidates = [2], target = 1
Output: []

Constraints

• 1 <= candidates.length <= 6
• 2 <= candidates[i] <= 12 (distinct)
• 1 <= target <= 15

Hints for Combination Sum

1. Hint 1

   Sort candidates; DFS with a 'start' index so combinations stay non-decreasing.

2. Hint 2

   Reusing a number means recursing with the SAME start index; break once a candidate exceeds the remainder.

How to solve Combination Sum

Two rules do all the work. Passing a start index forbids going back to a smaller candidate, which keeps every combination non-decreasing and stops the same multiset being found in several orders. Recursing with the same index rather than the next one is what allows a number to be reused without limit.

Approach

1. Sort candidates ascending — required both for the non-decreasing output and for the early break below.
2. Recurse with a start index and the remaining amount remain.
3. When remain hits exactly 0, the current list is a valid combination — record a copy.
4. Otherwise loop i from start: if candidates[i] > remain, break — everything further right is larger still, so no candidate can fit.
5. Append candidates[i] and recurse with start = i (not i + 1), so the same value can be picked again, then remove it.

Why it works

Every multiset that sums to the target has exactly one non-decreasing arrangement, and the start rule means the search builds only that arrangement — so each answer is found once and duplicates are impossible without any de-duplication step. remain reaching 0 is the exact success condition, and since all candidates are positive, remain strictly decreases, guaranteeing the recursion terminates.

Complexity

• Time — O(n^(target / min candidate))
• Space — O(target / min candidate)

Pitfalls

• Recurse with i, not i + 1. Using i + 1 bans reuse and silently solves a different problem.
• The sorted break is what makes this fast; continue would still be correct but explores branches that cannot possibly work.
• Test remain == 0 for success and let the break handle overshoot — a remain < 0 check without sorting still works, but with sorting it is unreachable.
• A target that cannot be formed must return an empty list, not a list holding an empty combination.

Reference solution

Python

from typing import List

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    s = sorted(candidates)
    out = []

    def go(start, remain, cur):
        if remain == 0:
            out.append(cur[:])
            return
        for i in range(start, len(s)):
            if s[i] > remain:
                break
            cur.append(s[i])
            go(i, remain - s[i], cur)
            cur.pop()

    go(0, target, [])
    return out

Java

public static int[][] combinationSum(int[] candidates, int target) {
    int[] s = candidates.clone();
    Arrays.sort(s);
    List<int[]> out = new ArrayList<>();
    List<Integer> cur = new ArrayList<>();
    goCombSum(out, s, 0, target, cur);
    return out.toArray(new int[0][]);
}

private static void goCombSum(List<int[]> out, int[] s, int start, int remain, List<Integer> cur) {
    if (remain == 0) {
        int[] snap = new int[cur.size()];
        for (int i = 0; i < cur.size(); i++) snap[i] = cur.get(i);
        out.add(snap);
        return;
    }
    for (int i = start; i < s.length; i++) {
        if (s[i] > remain) break;
        cur.add(s[i]);
        goCombSum(out, s, i, remain - s[i], cur);
        cur.remove(cur.size() - 1);
    }
}

C++

void goCombSum(vector<vector<int>>& out, vector<int>& s, int start, int remain, vector<int>& cur) {
    if (remain == 0) {
        out.push_back(cur);
        return;
    }
    for (int i = start; i < (int) s.size(); i++) {
        if (s[i] > remain) break;
        cur.push_back(s[i]);
        goCombSum(out, s, i, remain - s[i], cur);
        cur.pop_back();
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<int> s = candidates;
    sort(s.begin(), s.end());
    vector<vector<int>> out;
    vector<int> cur;
    goCombSum(out, s, 0, target, cur);
    return out;
}

JavaScript

var combinationSum = function(candidates, target) {
    const s = candidates.slice().sort(function(a, b) { return a - b; });
    const out = [];
    function go(start, remain, cur) {
        if (remain === 0) {
            out.push(cur.slice());
            return;
        }
        for (let i = start; i < s.length; i++) {
            if (s[i] > remain) break;
            cur.push(s[i]);
            go(i, remain - s[i], cur);
            cur.pop();
        }
    }
    go(0, target, []);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium