leetcode377

Posted on | In

377. 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.
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?

Idea

dp or memorized dfs: they are same in fact.

Code:

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
29
30
31
32
33
34
35
class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
#         memory = {}
#         nums.sort()
        
#         def dfs(target):
#             if target in memory:
#                 return memory[target]
            
#             res = 0
#             for num in nums:
#                 if num > target:
#                     break
#                 elif num == target:
#                     res += 1
#                 else:
#                     res += dfs(target - num)
#             memory[target] = res
#             return res       
#         return dfs(target)
        nums.sort()
        dp = [0] * (target + 1)
        dp[0] = 1 # if num == target
        for t in range(1, target + 1):
            for n in nums:
                if n > t:
                    break
                dp[t] += dp[t - n]
        print dp
        return dp[target]