# Backpack VI / Combination Sum IV

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

### 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

#### Dynamic Programming (Bottom Up Approach)

Combination Sum VI

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

``````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 %)

``````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%)

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