Combination Sum III

Java

class Solution {
				public List<List<Integer>> combinationSum3(int k, int n) {
						List<List<Integer>> result = new ArrayList<>();
						
						DFS(k, n, 1, new ArrayList<Integer>(), result);
						return result;
				}
				private void DFS(int k, int remain, int start, List<Integer> path, List<List<Integer>> result) {
						if (path.size() == k && remain == 0) {
						result.add(new ArrayList<>(path));	
						return;
						}
						if (path.size() > k || remain < 0) return;
						
						for (int i = start; i <= 9; i++) {
								if (i > remain) break;
								path.add(i);
								DFS(k, remain - i, i + 1, path, result);
								path.remove(path.size() - 1);
								}
				}
}