# Iterative solution (1ms) and recursive solution (2 ms) Java code

• `iterative solution using stack`

``````   public List<List<Integer>> combinationSum3Iterative(int k, int n) {
int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
int[] steps = new int[k];
int limit = 0, i = 0;
int remains = n;
boolean finish = false;
List<List<Integer>> list = new ArrayList<List<Integer>>();
while (limit != 0 || i < 9) {
// backtracking when can't find solution
while (i >= 9 || limit == k) {
if (limit == 0) {
finish = true;
break;
}
i = steps[--limit];
remains += a[i];
i++;
}
if (finish)
break;
if (a[i] < remains) {
steps[limit++] = i;
remains -= a[i];
i++;
continue;
} else if (a[i] == remains && limit == k - 1) {
List<Integer> nList = new ArrayList<Integer>(limit + 1);
for (int j = 0; j < limit; j++)
}
i = 9;
}
return list;
}
``````

`recursive solution`

``````public  List<List<Integer>> combinationSum3(int k, int n) {
int[] a = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
List<List<Integer>> list = new ArrayList<List<Integer>>();
combinationSumRecursiveHelper3(a, n, 0, list, new ArrayList<Integer>(), k);
return list;
}

public  void combinationSumRecursiveHelper3(int[] a, int target, int s, List<List<Integer>> list,
List<Integer> path, int space) {

for (int i = s; i < a.length; i++) {
if (target < a[i] || path.size() >= space)
return;
if (a[i] == target && path.size() == space - 1) {
List<Integer> l = new ArrayList<Integer>(path);