描述
给出一个都是正整数的数组 nums，其中没有重复的数。从中找出所有的和为 target 的组合个数。
样例
Example1
Input: nums = [1, 2, 4], and target = 4
Output: 6
Explanation:
The possible combination ways are:
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
[4]
Example2
Input: nums = [1, 2], and target = 4
Output: 5
Explanation:
The possible combination ways are:
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
思路
设为前i个数中所有和为target的组合个数。则
等于以
中所有元素为结尾的和。即
。具体实现如下所示。
class Solution {
public:
/**
* @param nums: an integer array and all positive numbers, no duplicates
* @param target: An integer
* @return: An integer
*/
int backPackVI(vector<int> &nums, int target) {
// write your code here
int n=nums.size();
if(!n)
{
return 0;
}
vector<vector<int>> dp(n+1,vector<int>(target+1,0));
for(int i=0;i<=n;i++)
{
dp[i][0]=1;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=target;j++)
{
for(int m=0;m<i;m++)
{
if(j-nums[m]>=0)
{
dp[i][j]+=dp[i][j-nums[m]];
}
}
}
}
return dp[n][target];
}
};
