1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| public class Q216 { public List<List<Integer>> combinationSum3(int k, int n) { int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}; List<List<Integer>> res = new ArrayList<>(); dfs(arr, n, k, 0, new Stack<>(), res); return res; }
private void dfs(int[] candidates, int n, int k, int index, Stack<Integer> temp, List<List<Integer>> res) { if (n == 0) { if (temp.size() == k) { res.add(new ArrayList<>(temp)); } return; } for (int i = index; i < candidates.length; i++) { if (candidates[i] > n || temp.size() == k) { return; } temp.push(candidates[i]); dfs(candidates, n - candidates[i], k, i + 1, temp, res); temp.pop(); } }
public static void main(String[] args) { new Q216().combinationSum3(3, 9).forEach(System.out::println); }
}
|