首页 > 其他 > 详细

[leetcode] 216 Combination Sum III

时间:2015-09-03 01:51:39      阅读:464      评论:0      收藏:0      [点我收藏+]

很基础的一道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;
    }
};


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

[leetcode] 216 Combination Sum III

原文:http://blog.csdn.net/nk_test/article/details/48186645

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!