[leetcode] 216 Combination Sum III

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