Backpack VI

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

Description

Given an integer arraynumswith all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integertarget.

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]

return6

Analysis & Solution

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

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

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