题目描述：

LeetCode 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?

题目大意：

给定一个无重复的正整数数组，计算得到一个目标正整数的所有可能组合方式的个数。

测试用例见题目描述。

注意不同的序列顺序应当视为不同的组合。

进一步思考：

如果数组中允许包含负数时应当怎样处理？

这会使问题作出怎样的变动？

如果允许负数需要对问题新增怎样的限制条件？

解题思路：

动态规划（Dynamic Programming）

状态转移方程：dp[x + y] += dp[x]

其中dp[x]表示生成数字x的所有可能的组合方式的个数。

Python代码：

class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        dp = [0] * (target + 1)
        dp[0] = 1
        for x in range(target + 1):
            for y in nums:
                if x + y <= target:
                    dp[x + y] += dp[x]
        return dp[target]

 

本文链接：http://bookshadow.com/weblog/2016/07/25/leetcode-combination-sum-iv/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码