class Solution { private List ls; private int n; private LinkedList path; private int k; private int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; public List> combinationSum3(int k, int n) { path = new LinkedList(); ls = new LinkedList(); this.n = n; this.k = k; dfs(0, 0, 0); return ls; } private void dfs(int i, int num, int count) { if (i > 9 || num > k || count > n) return; if (num == k && count == n) { //上面不能等于>= 9就跳出 不然很多需要9才能达到 num==k && count==n ls.add(path.clone()); return; } for (int x = i; x < 9; x++) { path.add(arr[x]); dfs(x + 1, num + 1, count + arr[x]); path.removeLast(); } } }
倒着遍历可以减少一些参数的设定
class Solution { private List ls; private LinkedList path; private int[] arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; public List> combinationSum3(int k, int n) { path = new LinkedList(); ls = new LinkedList(); dfs(8, n, k); return ls; } private void dfs(int k, int n, int num) { if ( n < 0||num < 0) return; if (num == 0 && n == 0) { ls.add(path.clone()); return; } for (int x = k; x >=0 ; x--) { path.add(arr[x]); dfs(x-1,n- arr[x],num-1); path.removeLast(); } } }