【题目描述】
Given an integer array nums with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Notice:
1. A number in the array can be used multiple times in the combination.
2. Different orders are counted as different combinations.
Example
Given nums = [1, 2, 4], target = 4
The possible combination ways are:
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
[4]
return 6
给出一个都是正整数的数组 nums，其中没有重复的数。从中找出所有的和为 target 的组合个数。
注意：
1. 一个数可以在组合中出现多次。
2. 数的顺序不同则会被认为是不同的组合。
样例
给出 nums = [1, 2, 4], target = 4
可能的所有组合有：
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
[4]
返回 6
【题目链接】
www.lintcode.com/en/problem/combination-sum-iv/
【题目解析】
动态规划（Dynamic Programming）
状态转移方程：dp[x + y] += dp[x]
其中dp[x]表示生成数字x的所有可能的组合方式的个数。
【参考答案】
网友评论