Given an array of distinct integers candidates and a target integer, return a list of all unique combinations of candidates where the chosen numbers sum to the target. The same number may be used an unlimited number of times. The combinations may be returned in any order, and two combinations are considered unique if the frequency of at least one chosen number differs.
Example
candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]
Two combinations sum to 7: 2 + 2 + 3 = 7 and 7 = 7. Each candidate can be reused, so using 2 twice is allowed.
Try each candidate repeatedly since unlimited use is allowed. If the running total equals the target, record the combination. If it exceeds the target, backtrack. A start index ensures you only use candidates at or after the current position, which prevents duplicate combinations like [2,3] and [3,2].
Why this works
You explore all possible combinations by trying each candidate and recursing with the updated total. Since candidates can be reused, the recursive call passes the same index i (not i+1). The start index prevents going backward, which eliminates duplicate orderings like [2,3] vs [3,2].
Step by step
- Base case: target reached — if the running total equals the target, save a copy of the current path.
- Prune overshooting — if the total exceeds the target, stop exploring this branch immediately.
- Try each candidate from start onward — this ensures combinations are built in non-decreasing index order, avoiding duplicates.
- Recurse with same index — pass
i(noti+1) because the same candidate can be reused unlimited times. - Backtrack — pop the last candidate to try the next option at this level.
Time: O(n^(T/M))
Space: O(T/M)
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), 0, result);
return result;
}
private void backtrack(int[] candidates, int target, int start, List<Integer> path, int total, List<List<Integer>> result) {
if (total == target) { // found a valid combination
result.add(new ArrayList<>(path));
return;
}
if (total > target) return; // overshot — prune this branch
for (int i = start; i < candidates.length; i++) {
path.add(candidates[i]);
backtrack(candidates, target, i, path, total + candidates[i], result); // stay at i since reuse is allowed
path.remove(path.size() - 1);
}
}
}
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> path;
backtrack(candidates, target, 0, path, 0, result);
return result;
}
private:
void backtrack(vector<int>& candidates, int target, int start, vector<int>& path, int total, vector<vector<int>>& result) {
if (total == target) { // found a valid combination
result.push_back(path);
return;
}
if (total > target) return; // overshot — prune this branch
for (int i = start; i < candidates.size(); i++) {
path.push_back(candidates[i]);
backtrack(candidates, target, i, path, total + candidates[i], result); // stay at i since reuse is allowed
path.pop_back();
}
}
};
def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
result = []
def backtrack(start, path, total):
if total == target: # found a valid combination
result.append(path[:])
return
if total > target: # overshot — prune this branch
return
for i in range(start, len(candidates)):
path.append(candidates[i])
backtrack(i, path, total + candidates[i]) # stay at i since reuse is allowed
path.pop()
backtrack(0, [], 0)
return result