Backpack IV

Problem 重复选择+唯一排列+装满可能性总数

Given n items with size nums[i] in an integer array with all positive numbers, no duplicates. An integer target denotes the size of a backpack. Find the number of possible ways to fill the backpack.

Each item may be chosen unlimited number of times

Example

Given candidate items [2,3,6,7] and target 7,

A solution set is:

[7]
[2, 2, 3]
return 2

Solution

public class Solution {
    public int backPackIV(int[] nums, int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 1; j <= target; j++) {
                if (nums[i] == j) dp[j]++;
                else if (nums[i] < j) dp[j] += dp[j-nums[i]];
            }
        }
        return dp[target];
    }
}