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

Each item may be chosen unlimited number of times

Have you met this question in a real interview?

Yes

Example

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

A solution set is: 
[7]
[2, 2, 3]
class Solution {

public:

/**

 * @param nums an integer array and all positive numbers, no duplicates

 * @param target an integer

 * @return an integer

 */

int backPackIV(vector<int>& nums, int target) {

    // Write your code here

    int n = nums.size();

    int k = target;

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

    f[0] = 1;

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

        for (int j = nums[i - 1]; j <= k; ++j) {

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

        }

    }

    return f[k];

}
};

results matching ""

    No results matching ""