C++ 0ms with mathematical exploration


  • 0
    N

    We can express the formula like this.
    Where a is the initial variable,
    a + (a+b_1) + (a+b_2) + ... + (a+b_(k-1))
    = ka + (b_1 + b_2 + ... + b_(k-1))

    a is max where the difference between b_(k-1) and b_k is 1 ( Sn = n(n+1)/2 ) -- (1)

    Thus, the problem is to get the maximum range of the set value.

    Maximize a ( a <= 1/k * (b_1 + b_2 + ... + b_(k-1)))

    from (1)

    = Maximize a ( a <= 1/k * (n - k(k-1)/2) )
    = Maximize a ( a <= n/k - (k-1)/2 )

    From the problem. minimum value is the next integer of the previous value which is inserted in the temporary set.

    So, we got the minimum value and the maximum value of a range.

    void next(vector<vector<int>> &ret, vector<int> &tmp, int minimum, int k, int n)
    {
    	if (minimum > n || (k == 1 && n > 9)) return;				// failed
    	if (k == 1)
    	{
    		tmp.push_back(n);
    		ret.push_back(tmp);
    		tmp.pop_back();
    		return;
    	}
    	int maximum = max((int)((double)(n / k) - (k - 1) / 2), 9);
    	for (int i = minimum; i <= maximum; i++)
    	{
    		tmp.push_back(i);
    		next(ret, tmp, i + 1, k - 1, n - i);
    		tmp.pop_back();
    	}
    }
    vector<vector<int>> combinationSum3(int k, int n) {
    	vector<vector<int>> ret;
    	vector<int> tmp;
    
    	next(ret, tmp, 1, k, n);
    	return ret;
    }

Log in to reply
 

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