> For the complete documentation index, see [llms.txt](https://code.taozirui.com/lc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code.taozirui.com/lc/dynamic-programming/backpack-problem/backpack-vi-aka-combination-sum-iv.md).

# Backpack VI aka: Combination Sum IV

## Problem 重复选择+不同排列+装满可能性总数 <a href="#articleheader28" id="articleheader28"></a>

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

## Notice <a href="#articleheader29" id="articleheader29"></a>

The different sequences are counted as different combinations.

## Example <a href="#articleheader30" id="articleheader30"></a>

Given nums = \[1, 2, 4], target = 4

The possible combination ways are:

```
[1, 1, 1, 1]
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]
[2, 2]
[4]
return 6
```

## Solution <a href="#articleheader31" id="articleheader31"></a>

```java
public class Solution {
    public int backPackVI(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 1; i <= target; i++) {
            for (int num: nums) {
                if (num <= i) dp[i] += dp[i-num];
            }
        }
        return dp[target];
    }
}
```