216.Combination Sum III

题目链接：https://leetcode.com/problems/combination-sum-iii/description/

题目大意：与39题类似，这里数组没有重复数字，就是从1到9，每个数字也不能重复选，且要求选的数字一共要是k个。

法一：利用39题的法一，直接暴力。代码如下（耗时2ms）：

 1     public List<List<Integer>> combinationSum3(int k, int n) {
 2         List<List<Integer>> res = new ArrayList<List<Integer>>();
 3         List<Integer> tmp = new ArrayList<Integer>();
 4         dfs(res, tmp, k, n, 1);
 5         return res;
 6     }
 7     public static void dfs(List<List<Integer>> res, List<Integer> tmp, int k, int n, int start) {
 8         if(tmp.size() == k) {
 9             int num = 0;
10             for(int i = 0; i < k; i++) {//计算和是否是n
11                 num += tmp.get(i);
12             }
13             if(num == n) {
14                 res.add(new ArrayList<Integer>(tmp));
15             }
16             return;
17         }
18         for(int i = start; i <= 9; i++) {
19             tmp.add(i);
20             dfs(res, tmp, k, n, i + 1);
21             tmp.remove(tmp.size() - 1);
22         }
23     }

View Code

剪枝，利用39题的第二种剪枝方法。代码如下（耗时1ms）：

 1     public List<List<Integer>> combinationSum3(int k, int n) {
 2         List<List<Integer>> res = new ArrayList<List<Integer>>();
 3         List<Integer> tmp = new ArrayList<Integer>();
 4         dfs(res, tmp, k, n, 1);
 5         return res;
 6     }
 7     public static void dfs(List<List<Integer>> res, List<Integer> tmp, int k, int n, int start) {
 8         if(tmp.size() == k && n == 0) {
 9             res.add(new ArrayList<Integer>(tmp));
10             return;
11         }
12         else if(n > 0) {
13             for(int i = start; i <= 9; i++) {
14                 //快速剪枝
15                 if(n < i) {
16                     break;
17                 }
18                 tmp.add(i);
19                 dfs(res, tmp, k, n - i, i + 1);
20                 tmp.remove(tmp.size() - 1);
21             }
22         }
23     }

View Code