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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

思路

一开始直接尝试利用暴力解法，直接利用回溯的方法来穷举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        return self.backtrack(nums, target, 0)
    def backtrack(self, nums, target, addup):
        ans = 0
        if (addup == target):
            return 1
        elif (addup < target):
            for i in nums:
                ans += self.backtrack(nums, target, addup + i)
            return ans
        else:
            return 0

可是用脚趾头想都是超时的。

在动态规划的第一步，我们是可以加入额外的空间对中间变量进行存储的。

递归调用的时候会调用很多次backtrack(n)。其中很多次，n都是重复的。在这里我们将中间变量存储为键值对。这样就可以减少复杂度了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        self.resultmap = {}
        ans = self.backtrack(nums, target)
        return ans
    def backtrack(self, nums, target):
        ans = 0
        if (target == 0):
            return 1
        elif (target > 0):
            for i in nums:
                if (self.resultmap.has_key(target - i)):
                    ans += self.resultmap[target - i]
                else:
                    current = self.backtrack(nums, target - i)
                    if (target - i > 0):
                        self.resultmap[target - i] = current
                    ans += current
            return ans
        else:
            return 0