# Backpack IV

## 重复选择+唯一排列+装满可能性总数

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

Each item may be chosen unlimited number of times

### Example

Given candidate items`[2,3,6,7]`and target`7`,

``````A solution set is:
[7]
[2, 2, 3]``````

## Analysis + Solution

#### 完全背包问题

``````public class Solution {
/**
* @param nums: an integer array and all positive numbers, no duplicates
* @param target: An integer
* @return: An integer
*/
public int backPackIV(int[] nums, int target) {
int n = nums.length;
int[][] dp = new int[n + 1][target + 1];
dp[0][0] = 1;
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++) {
dp[i][j] = dp[i - 1][j];
for (int k = 1; k * nums[i - 1] <= j; k++) {
dp[i][j] += dp[i - 1][j - k * nums[i - 1]];
}
}
}
return dp[n][target];
}
}``````

Or Similarly

``````    public int backPackIV(int[] nums, int target) {
int m = target;
int []A = nums;
int f[][] = new int[A.length + 1][m + 1];

f[0][0] = 1;
for (int i = 1; i <= A.length; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k * A[i-1] <= j; k++) {
f[i][j] += f[i-1][j-A[i-1]*k];
}
} // for j
} // for i
return f[A.length][target];
}``````

#### 优化空间复杂度为一维数组

``````    public int backPackIV(int[] nums, int target) {
int n = nums.length;
int[] dp = new int[target + 1];
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = nums[i - 1]; j <= target; j++) {
dp[j] += dp[j - nums[i - 1]];
}
}

return dp[target];
}``````

``````public class Solution {
public int backPackIV(int[] nums, int target) {

int n = nums.length;
int[] f = new int[target + 1];
f[0] = 1;
for (int i = 0; i < n; ++i) {
for (int j = nums[i]; j <= target; j++) {
f[j] += f[j - nums[i]];
}
}
return f[target];
}
}``````

## Reference

Jiuzhang Backpack Tutorial: https://www.jiuzhang.com/tutorial/backpack/471

Last updated