Given n items with sizenums[i]which an integer array and all positive numbers. An integertargetdenotes the size of a backpack. Find the number of possible fill the backpack.

Each item may only be used once

Have you met this question in a real interview?

Yes

Example

Given candidate items[1,2,3,3,7]and target7,

A solution set is: 
[7]
[1, 3, 3]

return2

class Solution {

public:

/\*\*

 \* @param nums an integer array and all positive numbers

 \* @param target an integer

 \* @return an integer

 \*/

int backPackV\(vector<int>& nums, int target\) {

    // Write your code here

    int n = nums.size\(\), k = target;

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

    f\[0\] = 1;

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

        for \(int j = k; j >= nums\[i - 1\]; --j\) {

            f\[j\] += f\[j - nums\[i - 1\]\];

        }

    }



    return f\[k\];

}

};