Combination Sum
Find distinct combinations of positive candidate values that sum to a target. Each value may be reused any number of times.
Work through the cases
3 examplesInput notation
Distinct positive candidates on line 1; positive target on line 2.Expected result
Sorted combinations in lexicographic order, one bracketed comma-separated list per line; or none.Case 1
Input
2 3 5 7
Expected output
[2,2,3] [2,5]
Case 2
Input
4 6 5
Expected output
none
Case 3
Input
2 4
Expected output
[2,2]
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
The first idea is to use each number any number of times and collect every sequence that sums to target. With n ≤ 30 and target ≤ 40, an unpruned search wastes paths that already exceed the target, and different orders of the same multiset would be counted twice. A combination ignores order, so each multiset should appear once. Sort first, and only take candidates from the current index rightward. After sorting, if the remainder s is already smaller than candidates[i], everything after is larger and the branch dies. dfs(i,s) enumerates j from i, and the recursive call stays at j so the same value may be reused.
We can first sort the array to facilitate pruning.
Next, we design a function dfs(i, s), which means starting the search from index i with a remaining target value of s. Here, i and s are both non-negative integers, the current search path is t, and the answer is ans.
In the function dfs(i, s), we first check whether s is 0. If it is, we add the current search path t to the answer ans, and then return. If s \lt candidates[i], it means that the elements of the current index and the following indices are all greater than the remaining target value s, and the path is invalid, so we return directly. Otherwise, we start the search from index i, and the search index range is j \in [i, n), where n is the length of the array candidates. During the search, we add the element of the current index to the search path t, recursively call the function dfs(j, s - candidates[j]), and after the recursion ends, we remove the element of the current index from the search path t.
In the main function, we just need to call the function dfs(0, target) to get the answer.
The time complexity is O(2^n × n), and the space complexity is O(n). Here, n is the length of the array candidates. Due to pruning, the actual time complexity is much less than O(2^n × n).
Similar problems:
- 40. Combination Sum II - 77. Combinations - 216. Combination Sum III
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int[] candidates;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
this.candidates = candidates;
dfs(0, target);
return ans;
}
private void dfs(int i, int s) {
if (s == 0) {
ans.add(new ArrayList(t));
return;
}
if (s < candidates[i]) {
return;
}
for (int j = i; j < candidates.length; ++j) {
t.add(candidates[j]);
dfs(j, s - candidates[j]);
t.remove(t.size() - 1);
}
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.