广州双城热恋创意文化传播有限公司

现在的位置: 主页 > 联系方式 > 文章列表

文章正文

[leetcode] 216 Combination Sum III

作者:广州双城热恋创意文化传播有限公司 来源:www.666loveyou.com 发布时间:2017-09-05 12:05:42
[leetcode] 216 Combination Sum III

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

class Solution { private: vector< vector >ans; vector 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 > combinationSum3(int k, int n) { dfs(k,n,0); return ans; } };

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:孝感网站建设 http://xiaogan.45qun.com


COPYRIGHT © 2015 广州双城热恋创意文化传播有限公司 ALL RIGHTS RESERVED.
网站地图 技术支持:肥猫科技
精彩专题:网站建设
购买本站友情链接、项目合作请联系客服QQ:2500-38-100