Given n items with sizenums[i]
which an integer array and all positive numbers, no duplicates. An integertarget
denotes 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];
}
};