LeetCode OJ：Combination Sum III（组合之和III）

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Ensure that numbers within the set are sorted in ascending order.

就是去k个数的和加起来等于n的组合的个数，数字只能取1-9，做法比较简单就是DFS吗，这里不再赘述，我比较喜欢用private变量，这样函数的参数式写出来比较简单：

 1 class Solution {
 2 public:
 3     vector<vector<int>> combinationSum3(int k, int n){
 4         size = k;
 5         target = n;
 6         vector<int> tmpVec;
 7         tmpVec.clear();
 8         ret.clear();
 9         dfs(tmpVec, target, 1);
10         return ret;
11     }
12     void dfs(vector<int>& vec, int left, int start)
13     {
14         if(left < 0) return;
15         if(left == 0 && vec.size() == size){ 
16             ret.push_back(vec);
17             return;
18         }
19         for(int i = start; i <= 9; ++i){
20             vec.push_back(i);
21             dfs(vec, left - i, i + 1);
22             vec.pop_back();
23         }
24     }
25 private:
26     vector<vector<int>> ret;
27     int target;
28     int size;
29 };

java版本的如下所示，方法仍然相同，简单的DFS：

 1 public class Solution {
 2     public List<List<Integer>> combinationSum3(int k, int n) {
 3         List<List<Integer>> ret = new ArrayList<List<Integer>>();
 4         List<Integer> tmp = new ArrayList<Integer>();
 5         dfs(ret, tmp, 0, k, 1, n); 
 6         return ret;  
 7     }
 8     
 9     public void dfs(List<List<Integer>>ret, List<Integer>tmp, int dep, int maxDep, int start, int left){
10         if(left < 0)
11             return; //回溯
12         else if(left == 0){
13             if(dep == maxDep)
14                 ret.add(new ArrayList<Integer>(tmp));
15             return;
16         }else{
17             for(int i = start; i <= 9; ++i){
18                 tmp.add(i);
19                 dfs(ret, tmp, dep+1, maxDep, i+1, left - i);
20                 tmp.remove(new Integer(i));
21             }
22         }
23     }
24 }

LeetCode OJ：Combination Sum III（组合之和III）

相关推荐