Difficulty: MediumBacktracking

Combination Sum

Problem in Plain English

Given distinct candidates and a target, return every unique combination that sums to the target while reusing any candidate as many times as needed. Each combination appears once regardless of internal order.

Problem Statement

Given an array of distinct integers candidates and an integer target, return every unique combination of candidates whose values sum to target.

Any candidate may be reused an unlimited number of times, and two combinations count as the same when they hold the same multiset of numbers.

Return the full list in any order.

Constraints

1 <= candidates.length <= 30
2 <= candidates[i] <= 40
All elements of candidates are distinct.
1 <= target <= 40
The input has fewer than 150 unique combinations summing to the target.

Examples

Example 1

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

Two copies of 2 and one 3 total 7; the candidate 7 also reaches the target alone. No other multiset works. [3,2,2] is the same multiset as [2,2,3], so it must not appear separately.

Example 2

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

Three multisets reach 8: four 2 values, [2, 3, 3], and [3, 5].

Example 3

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

No multiple of 2 equals 1, so the answer is empty.

Intuition

A combination records how many times each value is used, so [2,2,3] and [3,2,2] are the same answer. Backtracking grows a temporary path, explores its continuations, then removes the last choice before trying a sibling. In Example 1, two 2s leave 3 to reach 7. Allowing the same index again permits reuse; allowing only that index or later ones prevents different orders of the same multiset.

Approaches

Ordered Search + Dedup

Solution Details

Reveal Ordered Search + Dedup: intuition, complexity, and code

Intuition

Trying every candidate after every prefix explores all orderings, so each multiset shows up once per permutation. Sorting each finished path into a canonical key lets a set keep the first ordering and drop the rest.

Step-by-Step Logic

Start with an empty path and total 0. At every call, first accept an exact match or reject an overshoot; otherwise try every candidate. Example 1 uses [2,3,6,7] and target 7.
Append a candidate, recurse with the increased total, then remove that candidate when the call returns. The first branch reaches [2,2,2] at total 6; each next pick overshoots, so that entire branch returns without an answer.
At the parent path [2,2], the next choice 3 produces [2,2,3] at total 7. Copy and sort this path, use its canonical key in the set, and append it only if that key is new.
Continue every sibling branch. [2,3,2] and [3,2,2] reach 7 but have the existing key [2,2,3], so both are discarded. Overshooting calls return immediately.
The final root choice 7 records [7]. Once every root branch returns, the temporary path is empty and the result is [[2,2,3],[7]].

Why It Works

Each call explores every candidate as its next choice. Every valid multiset has at least one ordering, and that ordering is visited because all its prefix sums are at most the target. Positive candidates make every overshoot impossible to repair and guarantee termination. Only paths with the exact target sum are accepted. Sorting such a path creates the same key for all its permutations; the set admits each key once, so the result is complete and duplicate-free.

Dry Run

Ordered Search + Dedup: variable states at each step
path on entry	total	action	results so far
[]	0	try each candidate; undo each choice after return	[]
[2]	2	try each candidate; undo each choice after return	[]
[2,2]	4	try each candidate; undo each choice after return	[]
[2,2,2]	6	try each candidate; undo each choice after return	[]
[2,2,2,2]	8	overshoot; return	[]
[2,2,2,3]	9	overshoot; return	[]
[2,2,2,6]	12	overshoot; return	[]
[2,2,2,7]	13	overshoot; return	[]
[2,2,3]	7	record copy; return	[[2,2,3]]
[2,2,6]	10	overshoot; return	[[2,2,3]]
[2,2,7]	11	overshoot; return	[[2,2,3]]
[2,3]	5	try each candidate; undo each choice after return	[[2,2,3]]
[2,3,2]	7	duplicate key; return	[[2,2,3]]
[2,3,3]	8	overshoot; return	[[2,2,3]]
[2,3,6]	11	overshoot; return	[[2,2,3]]
[2,3,7]	12	overshoot; return	[[2,2,3]]
[2,6]	8	overshoot; return	[[2,2,3]]
[2,7]	9	overshoot; return	[[2,2,3]]
[3]	3	try each candidate; undo each choice after return	[[2,2,3]]
[3,2]	5	try each candidate; undo each choice after return	[[2,2,3]]
[3,2,2]	7	duplicate key; return	[[2,2,3]]
[3,2,3]	8	overshoot; return	[[2,2,3]]
[3,2,6]	11	overshoot; return	[[2,2,3]]
[3,2,7]	12	overshoot; return	[[2,2,3]]
[3,3]	6	try each candidate; undo each choice after return	[[2,2,3]]
[3,3,2]	8	overshoot; return	[[2,2,3]]
[3,3,3]	9	overshoot; return	[[2,2,3]]
[3,3,6]	12	overshoot; return	[[2,2,3]]
[3,3,7]	13	overshoot; return	[[2,2,3]]
[3,6]	9	overshoot; return	[[2,2,3]]
[3,7]	10	overshoot; return	[[2,2,3]]
[6]	6	try each candidate; undo each choice after return	[[2,2,3]]
[6,2]	8	overshoot; return	[[2,2,3]]
[6,3]	9	overshoot; return	[[2,2,3]]
[6,6]	12	overshoot; return	[[2,2,3]]
[6,7]	13	overshoot; return	[[2,2,3]]
[7]	7	record copy; return	[[2,2,3],[7]]
[] restored	0	all root branches finished; return	[[2,2,3],[7]]

Complexity Analysis

Time Complexity

O(V + Hk\log(k+1))

Space Complexity

O(k+L)

Let n be the candidate count, k = floor(target / minimum candidate), V the number of recursive calls including overshoots, H the number of exact-sum ordered paths, and L the number of scalar values across the unique returned lists. Every explored edge costs constant work; each of H hits copies and sorts at most k numbers and hashes its key. Expected set operations give the stated time. V can grow exponentially; a loose bound is O(n^(k+1)) for n >= 2, while n = 1 has O(k) calls. The stack/path use O(k), and the set plus results use O(L); only unique keys survive, not every permutation. Auxiliary space excluding the returned lists still includes O(L) dedup keys in Python and JavaScript. Java shares each accepted list between the set and output.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public List<List<Integer>> combinationSum(int[] candidates, int target) {5        List<List<Integer>> res = new ArrayList<>();6        Set<List<Integer>> seen = new HashSet<>();7        dfs(candidates, target, 0, new ArrayList<>(), res, seen);8        return res;9    }10
11    private void dfs(int[] candidates, int target, int total, List<Integer> path,12                     List<List<Integer>> res, Set<List<Integer>> seen) {13        if (total == target) {14            // Canonicalize a copy: all permutations must share one immutable set key.15            List<Integer> key = new ArrayList<>(path);16            Collections.sort(key);17            if (seen.add(key)) res.add(key);18            return;19        }20        if (total > target) return;21        for (int c : candidates) {22            path.add(c);23            dfs(candidates, target, total + c, path, res, seen);24            path.remove(path.size() - 1);25        }26    }27}

Hints

Hint 1

Unlimited reuse means the same candidate can follow itself, so your recursion must be allowed to stay in place rather than always move forward.

Hint 2

Trying candidates in every order finds the same multiset many times, so force a nondecreasing order with a start index.

Hint 3

Sort first: then any candidate that overshoots the remainder lets you break the loop instead of scanning the rest.

Edge Cases

No solution: [2] with target 1 returns [], because even the smallest candidate is too large.
One candidate can be reused: [2] with target 8 returns [[2,2,2,2]].
A candidate equal to target is a singleton answer; [7] with target 7 returns [[7]].
Unsorted input [7,3,2,6] with target 7 has the same two answers as Example 1. Numeric sorting is required only for the pruning approach.
At the maximum target 40, candidate 2 builds a path of length 20. Positive values bound recursion depth; zero or negative values would invalidate this argument.

Common Mistakes and Interview Tips

Always advancing the index after taking a candidate, which bans reuse and misses answers like [2, 2, 3].
Skipping the sort and the start index, which emits permutations of the same combination as if they were different answers.
Breaking on overshoot without sorting first, which wrongly discards larger-looking candidates that appear before smaller ones.
Saving the mutable path itself lets subsequent pops erase earlier answers; copy every accepted path.
Confusing runtime with result count: the ordered approach can explore many permutations even when the number of unique answers is small. Explain this trade-off in an interview.

Key Takeaway

Unlimited-reuse searches stay duplicate-free by imposing an order: sort the choices and let each position pick only from its own index onward.