216 Combination Sum III – Medium
Problem:
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Ensure that numbers within the set are sorted in ascending order.
Example 1:Input: k = 3, n = 7 Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
Thoughts:
This problem is modified based the Combination Sum II.
Difference is:
Candidates are numbers from 1 – 9 instead of given array.
Secondly, there is no constraints on number of elements in version II, but in III, the list of elements that adds up to given target value n has to have exact k elements.
Below is using an approach that’s modified based on the solution to Version II.
Solutions:
public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
if (k > 9 || n > 45) {
return result;
}
dfs(result, k, n, new LinkedList<Integer>(), 1);
return result;
}
private void dfs(List<List<Integer>> result, int k, int n, List<Integer> curr, int start) {
if (k == 0) {
if (n == 0) {
result.add(new LinkedList<Integer>(curr));
}
return;
}
for (int i = start; i <= 9; i ++) {
if ((9 - i) < k - 1) {
return;
}
curr.add(i);
dfs(result, k - 1, n - i, curr, i + 1);
curr.remove(curr.size() - 1);
}
}
}