C++ 0ms solution...


  • 0
    P
    class Solution {
    	void fill(vector<vector<int>> &result, vector<int>& nums, int n, int k) {
    		int last = nums[k];
    		if (k == 1) {
    			if (n >= last) {
    				return;
    			}
    			nums[0] = n;
    			result.push_back(nums);
    			return;
    		}
    
        	int max = std::min(last - 1, n - k * (k - 1) / 2);
    
        	for (int i = max; i > n / k; --i) {
        		nums[k - 1] = i;
        		fill(result, nums, n - i, k - 1);
        	}
    	}
    public:
        vector<vector<int>> combinationSum3(int k, int n) {
        	vector<vector<int>> result;
    
        	if (k <= 0 || k > 9) {
        		return result;
        	}
        	if (2 * n < k * (k + 1) || 2 * n > (19 - k) * k) {
        		return result;
        	}
    
        	int max = std::min(9, n - k * (k - 1) / 2);
        	if (k == 1) {
        		result.push_back(vector<int>(1, n));
        		return result;
        	}
    
        	vector<int> nums(k);
        	for (int i = max ; i > n / k; --i) {
        		nums[k - 1] = i;
        		fill(result, nums, n - i, k - 1);
        	}
    
        	return result;
        }
    };

Log in to reply
 

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