# 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) {
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) {
}
return;
}
for (int i = start; i <= 9; i ++) {
if ((9 - i) < k - 1) {
return;
}