> For the complete documentation index, see [llms.txt](https://aaronice.gitbook.io/lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://aaronice.gitbook.io/lintcode/knapsack_problems/backpack-vi.md).

# Backpack VI

## 重复选择+不同排列+装满可能性总数

### Description

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`.

> A number in the array can be used multiple times in the combination.\
> Different orders are counted as different combinations.

### Example

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`

## Analysis & Solution

和Backpack IV不同，那一题是唯一的排列，这一题里相同元素组合的不同排列也要计入总数。

因此，外层循环不再是元素本身，而是大小.

#### Dynamic Programming (Bottom Up Approach)

Combination Sum VI

```java
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] comb = new int[target + 1];
        comb[0] = 1;
        for (int i = 1; i < comb.length; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i - nums[j] >= 0) {
                    comb[i] += comb[i - nums[j]];
                }
            }
        }
        return comb[target];
    }
}
```

Backpack VI

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

#### Search + Memoization (Top Down Approach)

Using HashMap to store results **(Runtime: 4 ms, faster than 18.47 %)**

```java
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    public int combinationSum4(int[] nums, int target) {
        int count = 0;
        if (nums == null || nums.length ==0 || target < 0 ) return 0;
        if ( target == 0 ) return 1;
        if (map.containsKey(target)) return map.get(target);
        for (int num: nums){
            count += combinationSum4(nums, target-num);
        }
        map.put(target, count);
        return count;
    }
}
```

**Better Performance - Using dp\[] array (Runtime: 0 ms, faster than 100.00%)**

```java
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        Arrays.fill(dp, -1);
        dp[0] = 1;
        return helper(nums, target, dp);

    }
    private int helper(int[] nums, int target, int[] dp) {
        if (dp[target] != -1) return dp[target];
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (target >= nums[i]) {
                res += helper(nums, target - nums[i], dp);
            }
        }
        dp[target] = res;
        return res;
    }
}
```