0ms c++ backtracking


  • 0
    C
    //Combination III
    //限制了一定要用到k个数字来组合
    //限制装填数量的背包问题
    class Solution {
    public:
    vector<vector<int>> combinationSum3(int k, int n) {
    
    	vector<vector<int>> result;
    	vector<int> vc;
    
    	if (pow(9, k) < n)
    		return result;
    	if (n < k)
    		return result;
    
    	helper(k, n, vc, result,1, 11);
    	return result;
    }
    private:
    void helper(int k, int n, vector<int>& vc, vector<vector<int>>& result, int s, int e)
    {
    	if (s == e)
    		return;
    	for (int i = s; i < e; i++)
    	{
    		if (vc.size() > k)
    			return;
    		if (n == 0)
    		{
    			if (vc.size() == k){
    				result.push_back(vc);
    			}
    			return;
    		}
    		else if (n > 0){
    			int n2 = n - i;
    			vc.push_back(i);
    			helper(k, n2, vc, result, i + 1, e);
    			vc.pop_back();
    		}
    		else
    			return;
    	}
    }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.