Description

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

Notice

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

Solution

这一题和Backpack IV, V的区别是放置的顺序和位置无关，因此[1, 1, 2]和[1, 2, 1]被认为是两个不同的组合。
不同于前面几题一维数组是二维dp的优化，这是一个真正的一维dp问题-- 对于体积j的背包，遍历数组中所有的元素，讨论放入第i个元素的可能性。
因此外层是对体积的遍历，内层是对元素数组的遍历。

public class Solution {
    /**
     * @param nums an integer array and all positive numbers, no duplicates
     * @param target an integer
     * @return an integer
     */
    public int backPackVI(int[] nums, int target) {
        // Write your code here
        int[] dp = new int[target+1];
        dp[0] = 1;
        for (int j = 0; j <= target; j++) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= j) {
                    dp[j] += dp[j-nums[i]];
                }
            }
        }
        return dp[target];
    }
}