Lintcode 562. Backpack IV

Given an integer array nums[] which contains n unique positive numbers, num[i] indicate the size of ith item. An integer target denotes the size of backpack. Find the number of ways to fill the backpack.

Each item may be chosen unlimited number of times

Example

Example1

Input: nums = [2,3,6,7] and target = 7
Output: 2
Explanation:
Solution sets are: 
[7]
[2, 2, 3]

Example2

Input: nums = [2,3,4,5] and target = 7
Output: 2
Explanation:
Solution sets are: 
[2, 5]
[3, 4]

Code (Java):

public class Solution {
    /**
     * @param nums: an integer array and all positive numbers, no duplicates
     * @param target: An integer
     * @return: An integer
     */
    public int backPackIV(int[] nums, int target) {
        if (nums == null || nums.length == 0 || target < 0) {
            return 0;
        }
        
        int[] dp = new int[target + 1];
        dp[0] = 1;
        
        for (int i = 1; i <= nums.length; i++) {
            for (int j = 1; j <= target; j++) {
                int ans = dp[j];
                if (j - nums[i - 1] >= 0) {
                    ans += dp[j - nums[i - 1]];
                }
                
                dp[j] = ans;
            }
        }
        
        return dp[target];
    }
}