Given an integer arraynumswith all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integertarget.

Notice

A number in the array can be used multiple times in the combination.
Different orders are counted as different combinations.

Have you met this question in a real interview?

Yes

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]

return6

line 19 i start from 1 not nums[0]

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

    if \(target == 0\) {

        return 1;

    }

    if \(nums.empty\(\)\) {

        return 0;

    }

    int n = nums.size\(\);

    vector<int> f\(target + 1, 0\);

    f\[0\] = 1;

    for \(int i = 1; i <= target; ++i\) {

        for \(int num : nums\) {

            if \(num <= i\) {

                f\[i\] += f\[i - num\];

            }

        }

    }

    return f\[target\];

}

};