Combination Sum IV

题目

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]

target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 
7

思路分析

这道题首先也可以用DFS来实现，但是这道题与之前的3道Combination Sum题最大的不同是：其他三道题求的都是所有解的信息，而这道题要求的是解的个数。

这道题的解中可以有不同的排列组合方式，所以用DFS的时候要重点考虑递归的边界问题，之前的递归的下限基本都是startIndex，不管是不是包含这个startIndex，而这道题每一次递归都可以是数组的第一个数字开始遍历：for i in range(0, len(nums)):

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        def dfs(nums, target):
            if target < 0: return 
            if target == 0:
                self.result += 1
                return
            for i in range(0, len(nums)):
                if nums[i] > target: return
                dfs(nums, target-nums[i])
        self.result = 0
        dfs(sorted(nums), target)
        return self.result