Combination Sum III

题目

Find all possible combinations ofknumbers that add up to a numbern, 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]]

思路分析

这道题的思路也是标准的DFS实现，本题中没有给定一个数组，但是要求是用1-9的数字，那么相当于这个数组的内容也是定的，range(1,10)，n就是target，当找到sum为target时，还要判断组成sum的数字的个数是不是为k，是k就放到result中。而这道题与之前的题目相比，就不需要对数组进行排序了。

class Solution(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        def dfs(k, n, startIndex, path, result):
            if n < 0: return
            if n == 0: 
                if k == 0:
                    result.append(path)
                    return
            for i in range(startIndex, 10):
                if n<i: return
                dfs(k-1, n-i, i+1, path+[i], result)
        result = []
        dfs(k, n, 1, [], result)
        return result