Given n items with sizenums[i]which an integer array and all positive numbers, no duplicates. An integertargetdenotes the size of a backpack. Find the number of possible fill the backpack.

Each item may be chosen unlimited number of times

Have you met this question in a real interview?

Yes

Example

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

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

return2

public class Solution {
    /**
     * @param nums an integer array and all positive numbers, no duplicates
     * @param target an integer
     * @return an integer
     */

    //so transfer this to for each possible size, what's the number of possible fill
    //last step: 1. the first i - 1 already fill the back pack, 
    //           2. the last one can enter the back pack k times
    //we need to know the first i - 1 number of fills, sub problem
    //set f[i][j] represents the number of fill using the first i item to do size j
    //f[i][j] = f[i - 1][j] + f[i][j - A[i - 1]]
    //ans is f[n][target]
    //f[i][0] = 1
    //f[0][j] = 0
    public int backPackIV(int[] A, int target) {
        // Write your code here
        if (target == 0) {
            return 1;
        }

        int n = A.length;
        int[][] f = new int[n + 1][target + 1];

        int i, j;
        //init
        for (i = 0; i <= n; i++) {
            f[i][0] = 1;
        }

        for (j = 1; j <= target; j++) {
            f[0][j] = 0;
        }

        for (i = 1; i <= n; ++i) {
            for (j = 1; j <= target; ++j) {
                f[i][j] = f[i - 1][j];
                if (j - A[i - 1] >= 0) {
                    f[i][j] += f[i][j - A[i - 1]];
                }
            }
        }

        return f[n][target];


    }
}

optimize space complexity O(target)

public class Solution {
    /**
     * @param nums an integer array and all positive numbers, no duplicates
     * @param target an integer
     * @return an integer
     */

    //so transfer this to for each possible size, what's the number of possible fill
    //last step: 1. the first i - 1 already fill the back pack, 
    //           2. the last one can enter the back pack k times
    //we need to know the first i - 1 number of fills, sub problem
    //set f[i][j] represents the number of fill using the first i item to do size j
    //f[i][j] = f[i - 1][j] + f[i][j - A[i - 1]]
    //ans is f[n][target]
    //f[i][0] = 1
    //f[0][j] = 0
    public int backPackIV(int[] A, int target) {
        // Write your code here
        if (target == 0) {
            return 1;
        }

        int n = A.length;
        int[] f = new int[target + 1];

        int i, j;
        //init
        f[0] = 1;

        for (j = 1; j <= target; j++) {
            f[j] = 0;
        }

        for (i = 1; i <= n; ++i) {
            for (j = 1; j <= target; ++j) {
                if (j - A[i - 1] >= 0) {
                    f[j] += f[j - A[i - 1]];
                }
            }
        }

        return f[target];


    }
}