描述

給出一個(gè)都是正整數(shù)的數(shù)組 nums，其中沒有重復(fù)的數(shù)。從中找出所有的和為 target 的組合個(gè)數(shù)。

樣例

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]

思路

設(shè)為前i個(gè)數(shù)中所有和為target的組合個(gè)數(shù)。則等于以中所有元素為結(jié)尾的和。即。具體實(shí)現(xiàn)如下所示。

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];
    }
};