Problem overview
The function combination_sum receives a vector of distinct integers, candidates, and a target. It returns every combination of candidates that adds up to target. A candidate can be used as many times as you like. Two combinations are the same when they use the same numbers the same number of times, so [2, 2, 3] and [3, 2, 2] are one combination and must appear once.
The answer has a fixed shape: each combination is in ascending order, and the combinations are in lexicographic order, which means the first position where two combinations differ decides which comes first. If nothing adds up to target, the result is an empty vector.
With candidates = [5, 2, 3] and target = 8, the answer is [[2, 2, 2, 2], [2, 3, 3], [3, 5]]. The candidates aren't sorted, but every combination is. [2, 2, 2, 2] comes before [2, 3, 3] because their second numbers are 2 and 3.
Approach: build combinations one number at a time
The search builds a combination by choosing a number, then asking what is still needed. After choosing 2 for a target of 7, 5 remains, and the same question is asked again with 5. When the remainder is exactly 0, the numbers chosen so far are a complete combination. When the next candidate is larger than the remainder, it can't be used.
Two decisions make the answer correct without any cleanup:
- Sort the candidates first. Then every combination is built in ascending order, and the loop can stop at the first candidate that is too big, because all the later ones are bigger still.
- Only try candidates from the last chosen position onward. The next number is either the same as the last one (allowed, since numbers repeat) or a later, larger one. That way
[2, 2, 3]is built and[3, 2, 2]never is, so each combination appears exactly once. Trying all candidates at every step would produce every ordering: for[2, 3, 6, 7]and target 7, it gives[[2, 2, 3], [2, 3, 2], [3, 2, 2], [7]].
The sorted order also gives the lexicographic order of the output for free. The search tries smaller numbers first at every position, so combinations are found in the order the answer asks for.
This trace shows the search for [2, 3, 6, 7] with target 7. Each line is a call, indented by depth, and a "stop" line is a loop ended early because of a candidate that is too big:
current=[] remaining=7 i=0
current=[2] remaining=5 i=0
current=[2, 2] remaining=3 i=0
current=[2, 2, 2] remaining=1 i=0
stop at 2
current=[2, 2, 3] remaining=0 i=1
stop at 6
current=[2, 3] remaining=2 i=1
stop at 3
stop at 6
current=[3] remaining=4 i=1
current=[3, 3] remaining=1 i=1
stop at 3
stop at 6
current=[6] remaining=1 i=2
stop at 6
current=[7] remaining=0 i=3
Two calls end with remaining=0: [2, 2, 3] and [7], so the answer is [[2, 2, 3], [7]]. The call with [2, 2, 2] has 1 left, but the smallest candidate is 2, so it ends at once. The 6 appears as a dead end for the same reason.
Step by step
- Sort the candidates in place. The parameter is declared
mut, socandidates.sort()can reorder it. - Create
resultwithVec::new(). Rust works out that it is aVec<Vec<i32>>from how it is used. - Start the search. Call
Self::backtrackwith the candidates borrowed, the fulltargetas the amount still needed,0as the first index that may be used, a new empty vector for the combination being built, and&mut result. - Return
result.backtrackadded to the same vector, so it now holds everything. - Write the helper's signature.
remainingis how much the combination still needs,iis the first index it may use,currentis the combination so far, andresultcollects the finished ones. - Check for a finished combination. If
remaining == 0, the numbers incurrentadd up to the target. - Save a copy and return.
currentkeeps changing as the search continues, soresultgets a snapshot made withclone(). - Loop over the allowed candidates.
jgoes overi..candidates.len(). Starting atiinstead of 0 is what builds each combination once. - Stop at a candidate that is too big. If
candidates[j] > remaining,break: the later candidates are even bigger. - Choose the candidate by pushing it onto
current. - Complete the choice with a recursive call:
remaining - candidates[j]is what is left, and passingj, notj + 1, lets the same number be chosen again. - Undo the choice with
current.pop(), so the loop can try the next candidate in its place.
The solution in Rust
impl Solution {
fn combination_sum(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
candidates.sort();
let mut result = Vec::new();
Self::backtrack(&candidates, target, 0, &mut Vec::new(), &mut result);
result
}
fn backtrack(candidates: &Vec<i32>, remaining: i32, i: usize, current: &mut Vec<i32>, result: &mut Vec<Vec<i32>>) {
if remaining == 0 {
result.push(current.clone());
return;
}
for j in i..candidates.len() {
if candidates[j] > remaining {
break;
}
current.push(candidates[j]);
Self::backtrack(candidates, remaining - candidates[j], j, current, result);
current.pop();
}
}
}
Rust details worth knowing:
&mut Vec::new()as an argument. The temporary empty vector lives until the end of the statement, which is long enough for the whole search. Nothing else needs it afterwards, because every finished combination is copied intoresult.- Why
clone().currentis a mutable borrow of one vector that the search keeps pushing to and popping from. Pushing it directly intoresultisn't possible, sinceresultneeds to own its vectors, andclone()gives it a separate copy. - Passing borrows on.
candidates,currentandresultare already references insidebacktrack, so the recursive call passes them as they are. Rust reborrows the mutable ones for the length of the call. - Index types.
iandjareusize, because they index a vector, whileremainingand the candidates arei32. The rangei..candidates.len()excludes its end, sojis always a valid index. - A function that returns nothing.
backtrackhas no return type, so it returns(), and the barereturn;exits it early.
Complexity
Time: exponential. With n candidates, a target t and a smallest candidate m, a combination has at most t / m numbers, and each of them is one of n candidates, so the time is O(n^(t/m)) in the worst case. Sorting adds O(n log n), which doesn't change that. Each saved combination is also copied, but its length is at most t / m.
Space: besides the answer, O(t / m): the combination being built and one recursive call per number in it.
Edge cases and common mistakes
- No combination.
[2]with target 1 gives[]: the only candidate is bigger than the target, so the loop breaks on its first step and nothing is saved.[7, 3, 2]with target 1 gives[]as well. - One number repeated.
[3]with target 9 gives[[3, 3, 3]]. The recursive call must passjfor that to happen. - Passing
j + 1. Each number could then be used at most once, and[2, 2, 3]would be missed. - Passing
0instead ofj. Every ordering of a combination would be found, so the answer would have duplicates. - Forgetting to sort. Unsorted input would give combinations in the wrong order, and
breakwould stop too early, since a smaller candidate could come after a larger one. - Pushing
currentwithout copying. A shared vector would be emptied again by thepopcalls, and the saved combinations would change after the fact. This is why the lesson clones. - Using
continueinstead ofbreak. The answer stays the same, but the loop wastes time on candidates that are known to be too big.
Testing
[2, 3, 6, 7]with target 7 gives[[2, 2, 3], [7]].[5, 2, 3]with target 8 gives[[2, 2, 2, 2], [2, 3, 3], [3, 5]].[2]with target 1 gives[].[3]with target 9 gives[[3, 3, 3]].[2, 3]with target 6 gives[[2, 2, 2], [3, 3]].[2, 3, 5]with target 10 gives[[2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 3, 5], [5, 5]].
