> For the complete documentation index, see [llms.txt](https://junnie.gitbook.io/nine-chapter/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://junnie.gitbook.io/nine-chapter/9.dynamic-programming/92backpack/lintcode-563.backpack-v-m.md).

# 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];
    }
```