# Java DFS Solution with Comments

• ``````public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
// use dfs to solve this problem
// 9 level, each level represent if we need to add index
// each level has 2 branches
// when cur.size() == k and sum = n, add to result
// time complexity is O(2^9)
List<List<Integer>> res = new ArrayList<>();
List<Integer> cur = new ArrayList<>();
dfs(res, cur, k, n, 0, 1);
return res;
}

private void dfs(List<List<Integer>> res, List<Integer> cur, int k, int n, int sum, int index) {
if (cur.size() == k && sum == n) {
return;
}
if (index == 10) {
return;
}
dfs(res, cur, k, n, sum + index, index + 1);
cur.remove(cur.size() - 1);
dfs(res, cur, k, n, sum, index + 1);
}
}
``````

Solution2

``````public class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
// solution 2
// time complexity is O(9^k)
List<List<Integer>> res = new ArrayList<>();
List<Integer> cur = new ArrayList<>();
dfs(res, cur, k, n, 1);
return res;
}
private void dfs(List<List<Integer>> res, List<Integer> cur, int k, int remain, int start) {
if (k == 0) {
if (remain == 0) {
}
return;
}
for (int i = start; i < 10; i++) {
if (remain - i >= 0) {