Build a Target Sum by Reusing Candidates Freely
Solve this Problemcandidates, and a target. Find every distinct combination of candidates that adds up exactly to target — the same candidate can be picked as many times as needed, but no two combinations in the result should be the same multiset of values.
A brute-force search can find every one of these by extending every path it can think of and only checking the sum at the end (or, worse, checking it redundantly at every step without remembering it). The real win comes from carrying the running sum forward instead of recomputing it, and from cutting a branch the instant it's provably hopeless — sorting first turns "hopeless" into a single comparison instead of a search.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ candidates.length ≤ 15 - ◆
2 ≤ candidates[i] ≤ 30, and every value in candidates is distinct - ◆
1 ≤ target ≤ 40 - ◆
The same candidate may be reused any number of times within one combination
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Explore Every Extension, Check the Sum From Scratch
BruteWalk a decision tree where every node re-walks the entire current path to recompute its sum from zero — no running total is carried forward. A node whose sum matches target gets recorded, but nothing stops the search from continuing past that point: it keeps extending every path, even ones that already overshot target, until a fixed depth bound (target divided by the smallest candidate) is hit. That bound guarantees termination, but the search wastes real work both re-deriving sums it already knew and wandering down branches a smarter check would have cut off immediately.
O((target / min)ⁿ · n)O(target / min)1class Solution {
2 public int[][] combinationSum(int[] candidates, int target) {
3 List<int[]> result = new ArrayList<>();
4 List<Integer> path = new ArrayList<>();
5 int minVal = candidates[0];
6 for (int c : candidates) {
7 if (c < minVal) minVal = c;
8 }
9 int maxPicks = target / minVal;
10 explore(candidates, target, 0, path, result, maxPicks);
11 return result.toArray(new int[0][]);
12 }
13
14 private void explore(int[] candidates, int target, int start, List<Integer> path, List<int[]> result, int picksLeft) {
15 int sum = 0;
16 for (int v : path) sum += v;
17 if (sum == target) {
18 result.add(toArray(path));
19 }
20 if (picksLeft == 0) return;
21 for (int i = start; i < candidates.length; i++) {
22 path.add(candidates[i]);
23 explore(candidates, target, i, path, result, picksLeft - 1);
24 path.remove(path.size() - 1);
25 }
26 }
27
28 private int[] toArray(List<Integer> path) {
29 int[] row = new int[path.size()];
30 for (int j = 0; j < row.length; j++) row[j] = path.get(j);
31 return row;
32 }
33}Optimal — Sorted, Running Sum, Prune and Stop at Match
OptimalSort the candidates first, then carry the running sum down through the recursion instead of re-deriving it. Two savings follow directly from that: since candidates only grow moving right, the moment adding the next one would push the running sum past target, every candidate after it would too — break out of the loop right there instead of checking each one individually. And the instant a node's running sum equals target, record it and return immediately rather than continuing to extend an already-complete combination. Both cuts remove real, wasted branches the brute-force version always walks into.
O(n^(target / min))O(target / min)1class Solution {
2 public int[][] combinationSum(int[] candidates, int target) {
3 int[] sorted = candidates.clone();
4 Arrays.sort(sorted);
5 List<int[]> result = new ArrayList<>();
6 List<Integer> path = new ArrayList<>();
7 backtrack(sorted, target, 0, 0, path, result);
8 return result.toArray(new int[0][]);
9 }
10
11 private void backtrack(int[] sorted, int target, int start, int sum, List<Integer> path, List<int[]> result) {
12 if (sum == target) {
13 result.add(toArray(path));
14 return;
15 }
16 for (int i = start; i < sorted.length; i++) {
17 if (sum + sorted[i] > target) break;
18 path.add(sorted[i]);
19 backtrack(sorted, target, i, sum + sorted[i], path, result);
20 path.remove(path.size() - 1);
21 }
22 }
23
24 private int[] toArray(List<Integer> path) {
25 int[] row = new int[path.size()];
26 for (int j = 0; j < row.length; j++) row[j] = path.get(j);
27 return row;
28 }
29}