# 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]];
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/dynamic_programming/knapsack/backpack-iv.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.