Problem
Given an array of distinct integers candidates and an integer target, return all unique combinations of candidates where the chosen numbers sum to target.The same number may be chosen multiple times. The combinations may be returned in any order.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
candidates = [2,3,6,7]
target = 7 Output
[[2,2,3],[7]] Solution
This solution uses Backtracking to explore all possible combinations. At each step, a candidate is added to the current combination, and the remaining target is reduced by that value.If the remaining target becomes
0, a valid combination has been found and is added to the result. If it becomes negative, that path cannot produce a valid combination and is stopped.
After choosing a number, the recursion continues from the same index because the same candidate can be used multiple times. The
start index also prevents generating duplicate combinations in different orders, such as [2,3,2] and [3,2,2].
After each recursive call, the last number is removed so that the algorithm can explore the next possible combination.
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
backtrack(candidates, target, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] candidates, int remaining, int start,
List<Integer> current, List<List<Integer>> result) {
// A valid combination is found.
if (remaining == 0) {
result.add(new ArrayList<>(current));
return;
}
if (remaining < 0) {
return;
}
for (int i = start; i < candidates.length; i++) {
// Choose the current candidate.
current.add(candidates[i]);
// Reuse the same candidate if needed.
backtrack(candidates, remaining - candidates[i], i, current, result);
// Undo the choice.
current.remove(current.size() - 1);
}
}
Complexity
The algorithm explores possible combinations recursively, and the number of valid paths depends on the input values and the target. In the worst case, the time complexity isO(2n) or higher depending on the target and the candidate values.
The recursion depth and current combination can grow up to
O(target / minCandidate), excluding the space required for the output.