LintCode 563.Backpack V (M)

Given n items with size nums[i] which an integer array and all positive numbers. An integer target denotes the size of a backpack. Find the number of possible ways to fill the backpack. Each item may only be used once

Example

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

A solution set is: 
[7]
[1, 3, 3]

return 2 Solution:

    public int backPackV(int[] nums, int target) {

        int n = nums.length;
        if(n == 0 || target <= 0) return 0;
        // first i elements can fill j capcity in dp[i][j] ways
        // dp[i][j]
        int[][] dp = new int[n+1][target+1];
        
        //dp[0][...] = 0;
        //dp[...][0] = 1;
        for(int i = 0; i<= n; i++)
        {
            dp[i][0] = 1;
        }
        for(int j = 0; j<= target; j++)
        {
            dp[0][j] = 0;
        }

        dp[0][0] = 1;

        for(int i = 1; i<= n; i++)
        {
            for(int j = 1; j<= target; j++)
            {
                if(j-nums[i-1] >=0)
                {
                    dp[i][j] = dp[i-1][j]+ dp[i-1][j-nums[i-1]];
                }else
                {
                    dp[i][j] = dp[i-1][j];
                }
                
            }
        }

        return dp[n][target];
    }