"""
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.


Example 1:

Input: k = 3, n = 7

Output:

[[1,2,4]]

Example 2:

Input: k = 3, n = 9

Output:

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

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        sol = []
        nums = [1,2,3,4,5,6,7,8,9]
        self.dfs(nums, sol, 0, [], k, n)
        return sol
    
    def dfs(self, candidates, sol, index, loc_sol, count, remaining):
        if remaining < 0 or len(loc_sol) > count:
            return
        if remaining == 0 and len(loc_sol) == count:
            sol.append(loc_sol)
            return
        for i in range(index, len(candidates)):
            if candidates[i] > remaining:
                return
            if len(loc_sol) >= count:
                return
            self.dfs(candidates, sol, i+1, loc_sol+[candidates[i]], count, remaining - candidates[i])


if __name__ == '__main__':
        obj = Solution()
        k, n = 3, 9
        print "Input:", k, n
        print "Solution:", obj.combinationSum3(k, n)
