# Top down dynamic programming + some fundamental math

• Assume we have `k` numbers summing up to `n`, then there must be a number `m` that is maximum. Then we only need to find `k-1` numbers summing up to `n-m`. This gives us an iterative way of coding, or DP.

The fundamental math is that `m` has to satisfy some boundary conditions as explained in the coding.

Code in Java:

``````private List<List<Integer>> res;
public List<List<Integer>> combinationSum3(int k, int n) {
res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
helper(k, n, list);
for(List<Integer> l : res) // reverse order because the numbers were added in descending order in helper method
Collections.reverse(l);
return res;
}

//recursively check all possible combinations. add into the list if end up with k=n=0
private void helper(int k, int n, List<Integer> list) {
if(k<0 || n<0) return;
if(k==0 && n==0) {
return;
}
int maxUpperbound = n - k*(k-1)/2; // x1+x2+...+xk = n ==> max of xk = n - (1+2+...+(k-1))
if(maxUpperbound < k) return; // if xk < k, there is a duplicate
maxUpperbound = maxUpperbound > 9 ? 9 : maxUpperbound;
int minUpperbound = (2*n + (k-1)*k)/2/k; // x1+x2+...+xk = n, and assume x1<x2<...<xk, the min value for xk should be: xk + (xk-1) + (xk-2) + ... + (xk-(k-1)) = n, thus xk = (2*n + (k-1)*k)/2/k

for(int i=minUpperbound; i<=maxUpperbound; i++) {
if(list.size()>0) {
int min = list.get(list.size()-1);
if(i>=min) continue; // new upperbound cannot be equal to or greater than current min value in the list
}
List<Integer> innerList = new ArrayList<>(list);