# Combination Sum IV

## Backpack VI ([LI.564](http://www.lintcode.com/en/problem/backpack-vi/))

> Given an integer array sizes with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

## Example

```
I: sizes = [1,2,4], target = 4
O: [ [1,1,1,1], [1,1,2], [1,2,1], [2,1,1], [2,2], [4] ] = 6
```

## State Graph

![](/files/-LtpqYTouiKqYyfFLxtW)

## Code

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

## Better Code

```java
public int backPackVI(int[] sizes, int target) {
    // create memo table
    int[] kp = new int[target + 1];
    // init base case
    kp[0] = 1;
    // sort so we can break
    Arrays.sort(sizes);
    // topo order
    for (int s = 1; s <= target; s++) {
        for (int i = 0; i < sizes.length; i++) {
            if (sizes[i] > s) {
                break;
            }
            kp[s] += kp[s-sizes[i]];
        }
    }
    // final answer
    return kp[target];
}
```

## Combination Sum IV ([LC.377](https://leetcode.com/problems/combination-sum-iv/))

> Given an integer array with all positive numbers and no duplicates, find the number of possible *combinations* that add up to a positive integer target.

## Example

```
I: nums = [1,2,3], target = 4
O: [ [1,1,1,1], [1,1,2], [1,2,1], [1,3], [2,1,1], [2,2], [3,1] ] = 7
```

## Analysis

Combination sum as the name suggests, we want combinations. This is a full knapsack problem.

## Approach

```
1. Optimal subproblem
    cs[t] = maximum number of combinations to reach target t
2. Recurrence
    if nums[i] <= t: cs[t] += cs[t-nums[i]]
    else: cs[t] += 0
3. Topo Order
    for t from 1 to target
        for i from 0 to n-1
4. Base Case
    cs[0] = 1 b/c there's only one subset[] for target 0
5. Final Answer
    cs[target]
```

## Code

```java
public int combinationSum4(int[] nums, int target) {
    // create memo table
    int cs[] = new int[target + 1];
    // base case
    cs[0] = 1;
    // topo order
    for (int t = 1; t <= target; t++) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= t) {
                cs[t] += cs[t-nums[i]];
            }
        }
    }
    // final answer
    return cs[target];
}
```

## Better Code

```java
public int combinationSum4(int[] nums, int target) {
    // create memo table
    int cs[] = new int[target + 1];
    // base case
    cs[0] = 1;
    Arrays.sort(nums);
    // topo order
    for (int t = 1; t <= target; t++) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > t) {
                break;
            }
            cs[t] += cs[t-nums[i]];
        }
    }
    // final answer
    return cs[target];
}
```

## Time & Space Complexity

Time: O(n\*target) Space: O(target)


---

# 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/combination-sum-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.