[leetcode] 216 Combination Sum III

很基础的一道DFS，，开始的时候觉得可能剪枝要处理的好一些，于是我的剪枝是：如果当前的值合适，那么剩下的和一定要大于剩下的个数*1&&小于剩下的个数*9，这虽然不是最优，但是处理起来比较简单，没想到样例只有18组，跑了0ms，数据太水了。

class Solution {private: vector< vector<int> >ans;vector<int> v; public: void dfs(int num,int left,int cur) // 剩下的个数，剩下的值，当前值{if(num==0&&left==0){ans.push_back(v);}for(int i=1;i<=9;i++){if(i>cur&&left>=i&&left>=num&&left<=num*9){v.push_back(i);dfs(num-1,left-i,i);v.pop_back();}}}vector< vector<int> > combinationSum3(int k, int n) {dfs(k,n,0);return ans;}};

版权声明：本文为博主原创文章，未经博主允许不得转载。

走过一段路，风景毕竟不相同。这段惠风和畅，