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個數(shù)的和加起來等于n的組合的個數(shù)，數(shù)字只能取1-9，做法比較簡單就是DFS嗎，這里不再贅述，我比較喜歡用private變量，這樣函數(shù)的參數(shù)式寫出來比較簡單：

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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/-wang-cheng/p/4895864.html

總結(jié)

以上是生活随笔為你收集整理的LeetCode OJ：Combination Sum III（组合之和III）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。