描述

给出一个都是正整数的数组 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];
    }
};