程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> [leetcode] 216 Combination Sum III

[leetcode] 216 Combination Sum III

編輯:C++入門知識

[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;
    }
};


 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved