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变量，这样函数的参数式写出来比较简单：

 class Solution {

 public:

     vector<vector<int>> combinationSum3(int k, int n){

         size = k;

         target = n;

         vector<int> tmpVec;

         tmpVec.clear();

         ret.clear();

         dfs(tmpVec, target, );

         return ret;

     }

     void dfs(vector<int>& vec, int left, int start)

     {

         if(left < ) return;

         if(left ==  && vec.size() == size){

             ret.push_back(vec);

             return;

         }

         for(int i = start; i <= ; ++i){

             vec.push_back(i);

             dfs(vec, left - i, i + );

             vec.pop_back();

         }

     }

 private:

     vector<vector<int>> ret;

     int target;

     int size;

 };

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

 public class Solution {

     public List<List<Integer>> combinationSum3(int k, int n) {

         List<List<Integer>> ret = new ArrayList<List<Integer>>();

         List<Integer> tmp = new ArrayList<Integer>();

         dfs(ret, tmp, 0, k, 1, n);

         return ret;

     }

     public void dfs(List<List<Integer>>ret, List<Integer>tmp, int dep, int maxDep, int start, int left){

         if(left < 0)

             return; //回溯

         else if(left == 0){

             if(dep == maxDep)

                 ret.add(new ArrayList<Integer>(tmp));

             return;

         }else{

             for(int i = start; i <= 9; ++i){

                 tmp.add(i);

                 dfs(ret, tmp, dep+1, maxDep, i+1, left - i);

                 tmp.remove(new Integer(i));

             }

         }

     }

 }

巴特西

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

最新文章

热门文章