Problem overview
The method combinationSum receives an int[] candidates of distinct numbers and an int target. It returns every combination of candidates that adds up to target. A number may be used any number of times. Two combinations are the same when they use the same numbers the same number of times, so [2, 2, 3] and [3, 2, 2] count once. Each combination is written in ascending order, and the combinations are returned in lexicographic order: the first position where two of them differ decides which comes first. When nothing adds up to the target, the result is an empty list.
For candidates = [2, 3, 6, 7] and target = 7 the answer is [[2, 2, 3], [7]]: 2 + 2 + 3 and 7 alone. For candidates = [5, 2, 3] and target = 8 it is [[2, 2, 2, 2], [2, 3, 3], [3, 5]], even though the input is not sorted. For candidates = [2] and target = 1 it is [].
Approach: build one combination at a time
A combination is built number by number. At each point there is an amount still needed, remaining, and a partial combination, current. Trying every candidate as the next number, going deeper with the smaller remainder, and then removing the number again is backtracking. When remaining reaches 0, current adds up to the target, so it is saved.
Two ideas keep the search correct and small:
- Never go back to an earlier candidate. The loop that picks the next number starts at index
i, the index of the last number chosen, not at 0. A combination therefore takes its numbers in sorted order, and[2, 2, 3]is built but[3, 2, 2]never is. Each combination appears exactly once, with no need to remove duplicates afterwards. The loop starts at the same index, not the next one, because a number can be reused. - Sort first. With sorted candidates, combinations come out in ascending order, and the combinations come out in lexicographic order, which is the order the answer needs. Sorting also allows an early exit: once a candidate is bigger than
remaining, every later one is bigger too, so the loop can stop.
The search is exponential. With n candidates, a target t and a smallest candidate m, a combination has at most t / m numbers, and each is one of n candidates, so the worst case is O(n^(t/m)). The constraints keep this small enough: at most 30 candidates, each at least 2, and a target of at most 40.
Step by step
The outer method
- Sort
candidateswithArrays.sort. It sorts the array in place, ascending. - Create
result, aList<List<Integer>>backed by a newArrayList, to collect the combinations. - Start the search with
backtrack(candidates, target, 0, new ArrayList<>(), result): all of the target is still needed, any candidate from index 0 may be used, and the combination is empty. - Return
result.backtrackfilled the same list.
The helper backtrack
- Declare it as a
voidmethod taking the candidates,remaining, the first usable indexi, the partial combinationcurrentandresult. - If
remaining == 0, the numbers incurrentadd up to the target. - Save a copy with
result.add(new ArrayList<>(current))and return. The copy matters becausecurrentkeeps changing. Returning is safe because every candidate is at least 2, so adding more would overshoot. - Loop
jfromito the end ofcandidates: every number the combination may take next. - Break when
candidates[j]is bigger thanremaining. The array is sorted, so no later number fits either. - Choose the number by adding it to
current. - Recurse with
remaining - candidates[j]and the indexj, so the same number can be chosen again. - Undo the choice by removing the last element of
current, at indexcurrent.size() - 1. The loop then tries the next candidate.
The solution in Java
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), result);
return result;
}
void backtrack(int[] candidates, int remaining, int i, List<Integer> current, List<List<Integer>> result) {
if (remaining == 0) {
result.add(new ArrayList<>(current));
return;
}
for (int j = i; j < candidates.length; j++) {
if (candidates[j] > remaining) {
break;
}
current.add(candidates[j]);
backtrack(candidates, remaining - candidates[j], j, current, result);
current.remove(current.size() - 1);
}
}
}
Java details that matter here:
- Copy before saving. A
Listis a reference. Addingcurrentitself would store the same object that the search keeps editing. With the list[5, 1, 7]stored directly and then shortened by one element, the stored list shows[5, 1], while a copy made withnew ArrayList<>(current)still shows[5, 1, 7]. The same sharing would leave a result full of empty lists once the search has undone every choice. remove(int)versusremove(Object). On aList<Integer>,remove(current.size() - 1)passes anint, so it removes the element at that index. For[10, 20, 1],remove(1)gives[10, 1]: it removed the 20 at index 1, not the value 1. To remove by value you needremove(Integer.valueOf(1)), which on[10, 1]gives[10].- Autoboxing.
current.add(candidates[j])converts theintto anIntegerautomatically. - The diamond operator.
new ArrayList<>()as an argument takes its type from the parameter,List<Integer>. Arrays.sortchanges the caller's array. That is acceptable here, since the order ofcandidatesdoesn't matter to the caller of this lesson, but the method modifies its input.
Complexity
Time: O(n^(t/m)) in the worst case, with n candidates, target t and smallest candidate m. A combination has at most t / m numbers, and each one is chosen from at most n candidates. Sorting adds O(n log n), which is negligible next to the search.
Space: O(t / m) besides the answer: the combination being built and one call frame per number in it.
Edge cases and common mistakes
- No combination exists.
[2]with target 1 gives[], and so does[3, 5]with target 7. The loop breaks at once or the search runs out of options, andresultstays empty. - Starting the loop at 0. This finds every order of the same numbers, so
[2, 3, 3],[3, 2, 3]and[3, 3, 2]would all be added. - Passing
j + 1instead ofj. Each number could then be used only once, and[2, 2, 3]would never appear. - Forgetting to sort. The early
breakwould then skip candidates that still fit, and the output order would not be the required one. For[5, 2, 3]the result must still start with[2, 2, 2, 2]. - Storing
currentwithout copying, or forgetting the undo step. The first leaves wrong contents in the result; the second makes every later combination carry leftovers from earlier ones. - Using
remove(value)by mistake. As shown above, anintargument is an index. - Candidates that repeat in different sizes. A larger candidate can combine with itself as well as with smaller ones: for
[4, 2]and target 8, the answer includes[4, 4]as well as[2, 2, 4]and[2, 2, 2, 2].
Testing
[2, 3, 6, 7], target 7 gives[[2, 2, 3], [7]].[5, 2, 3], target 8 gives[[2, 2, 2, 2], [2, 3, 3], [3, 5]].[2], target 1 gives[].[3, 5], target 7 gives[].[2, 3, 5], target 8 gives[[2, 2, 2, 2], [2, 3, 3], [3, 5]].[4, 2], target 8 gives[[2, 2, 2, 2], [2, 2, 4], [4, 4]].[7, 3, 2], target 40 gives a list of 25 combinations.
