> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-2/dynamic_programming/knapsack/backpack-iv.md).

# Backpack IV

## Backpack IV ([LI.562](http://www.lintcode.com/en/problem/backpack-iv/))

> Given n items, an integer array sizes and a target, find the number of possible subsets of items to fill the backpack.

## Example

```
I: sizes=[2,3,6,7], target=7
O: [ [2,2,3], [7] ] = 2
```

Notice: `[2,3,2]` and `[3,2,2]` are not taken into account

## Analysis

Because we want subsets instead of combinations, this is a 0/1 knapsack problem.

## Approach 1

```
1. Optimal subproblem
    kp[s] = maximum number of ways to fill size s
2. Recurrence
    if s < size[i]: kp[s] += 0 do nothing
    else if size[i] <= s: kp[s] += kp[s-size[i]]
3. Topo Order (0/1 is different from full)
    for i from 0 to n-1
        for s from 1 to target
4. Base case
    kp[0] = 1
    b/c there's only one way to fill an empty bag (no items [] subset)
5. Final answer
    kp[target]
```

## State Graph 1

![](/files/-LtpqZoDY9S7bJbr6WUt)

## Code 1

```java
public int backPackIV(int[] sizes, int target) {
    // create memo table
    int[] kp = new int[target + 1];
    // init base case
    kp[0] = 1;
    // topo order
    for (int i = 0; i < sizes.length; i++) {
        for (int s = sizes[i]; s <= target; s++) {
            kp[s] += kp[s-sizes[i]];
        }
    }
    // final answer
    return kp[target];
}
```

## Approach 2

```
1. Optimal subproblems
    kp[i][s] = 
    maximum number of ways to fill out the target s with the first i items
2. Recurrence
    if sizes[i] <= s
        kp[i][s] += kp[i-1][s-sizes[i]]
3. Topo Order
    for i from 1 to n
        for s from 1 to target
4. Base case
    kp[0][s] = 0
    kp[i][0] = 1
5. Final Answer
    kp[n][target]
```

## State Graph 2

![](/files/-LtpqZoFyx3Km24Lz3L8)

## Code 2

```java
public int backPackIV(int[] sizes, int target) {
    // create memo table
    int n = sizes.length;
    int[][] kp = new int[n+1][target+1];
    // init base case
    for (int i = 0; i <= n; i++) {
        kp[i][0] = 1;
    }
    // topo order
    for (int i = 1; i <= n; i++) {
        for (int s = 1; s <= target; s++) {
            int k = 0;
            while (k*sizes[i-1] <= s) {
                kp[i][s] += kp[i-1][s-k*sizes[i-1]];
                k++;
            }
        }
    }
    // final answer
    return kp[n][target];
}
```

The recurrence below is wrong. It failed to enumerate all the occurrences of item i. Why does it differ from approach 1?

```java
if (sizes[i-1] <= s) {
    kp[i][s] += kp[i-1][s-sizes[i-1]];
}
```