Leetcode 216: Combination Sum III

[[1,2,4]]

[[1,2,6], [1,3,5], [2,3,4]]

from math import ceil

class Solution(object):
    
    def lower_bound(self, n, k):
        return int(ceil(float(2*n+k**2-k)/(2*k)))

    def upper_bound(self, n, k):
        return n-k*(k-1)/2 + 1

    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        if k < 1 or k > 9 or n > (9 + (9 -k + 1)) * k / 2:
            return []

    	return list(self._comb_sum(n,k, 10))
    
    def _comb_sum(self, n, k, last_i):
    	if k == 1:
    		yield [n]
    	else:
        	for i in xrange(self.lower_bound(n, k), min(last_i, self.upper_bound(n, k))):
    		    for res in self._comb_sum(n-i, k-1, i):
    			    yield res + [i]

Idea:

I am using some mathematical properties to solve this problem.

(1) if k<1 or k>9 or the largest k numbers in 1~9 sum is larger less than n, then the program should return an empty list. (line 17-18)

(2) To solve this problem by recursion, we call `_comb_sum` recursively. It has `n`, `k` and `last_i` as parameters.  Intuitively, the function calls `n-i`, `k-1` in the recursion while traversing `i` in a designated range.

The lower bound of the traversal range is that: $latex \sum\limits_{j=i-k+1}^{i} j = \frac{(2i-k+1) \cdot k}{2} \geq n$. That is, the largest $latex k$ number ending at $latex i$ should sum up larger than $latex n$. Any $latex i$ smaller than that will result $latex n-i$ being too large to be summed up by $latex k-1$ numbers smaller than $latex i$. Solving this inequality we get: $latex i \geq \frac{2n+k^2-k}{2k}$.

The upper bound of the traversal range is that: $latex 1+2+\cdots+(k-1) + i \leq n$. If $latex i$ is larger than that, you can’t use remaining $latex k-1$ numbers to sum up to $latex n-i$. One more constraint is that the upper bound should not equal to/exceed $latex i$ from the upper level of recursion. 

Some people solve this problem by dfs: https://discuss.leetcode.com/topic/15023/accepted-recursive-java-solution-easy-to-understand/2, https://discuss.leetcode.com/topic/15168/concise-python-solution-using-dfs

Although dfs is more readable, it wastes some time on unnecessary trials:

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        if k < 1 or k > 9 or n > (9+9-k+1)*k/2:
            return []

        res = []    
        self.dfs(n, k, 1, [], res)
        return res

    def dfs(self, n, k, start, cur, res):
        if k == 0: 
            if n == 0:
                res.append(list(cur))
        else:
            for i in xrange(start, 10):
                cur.append(i)
                self.dfs(n-i, k-1, i+1, cur, res)
                cur.pop()

        

Note that at line 18 you should add a copy of `cur` to `res`. Otherwise any change in `cur` will change that added to `res`.