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

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

在backpackV中
【2，1，1】和 【1，2，2】算一种组合，是因为我们先处理第一个物品，再处理第二个物品

在此题中上述情况会被算成两种组合，所以不能先处理第一个物品再处理第二个物品，与传统背包从前往后想不同，可以从后往前想去看最后一步。

假设我们想知道有多少种组合可以组成3这个重量，
那么如果最后一个位置是物品2，则剩下的部分重量是3 - 2，只要我们知道组成剩下物品重量的组合数就可以退出3这个重量

f[i] represents the possible combination of weight i

f[i] = f[i - A[0]] + f[i - A[1]] +....+ f[i - A[n - 1]]

//change this to the problem to solve how many combination for 1 till m
    //last step: in the best solution, last item size is Ak, then we need to know Target - Ak
    //sub problem
    //so we enumerate the last time size
    //f[i] represents when size is m how many different combination we can fufill the backpack

    //f[i] = f[i - A[0]] + f[i - A[1]] + f[i - A[n - 1]]
    //init
    //f[0] = 1
    //corner case
    //i >= A[k]

    public int backPackVI(int[] A, int target) {
        // Write your code here
        if (target == 0) {
            return 1;
        }

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

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

        return f[target];

    }