[LeetCode]Combination Sum IV

和Coin Change II是很类似的，都是knapsack problem的变形问题。唯一的不同就是同一个组合不同的排列也算不同的方法，比如背包容量为4，1，1，2和2，1，1和1，2，1都算不同的。而Coin Change II里这些都算相同的。那么之前的DP方程这一题就不适用了，因为没有办法算不同的排列。我们换一个思路，DP[i]表示背包容量为i的时候填满背包的所有组合数。我们有递推公式：

• DP[i] = sum(DP[i - c[j]])，where c[j]代表第j + 1个物品的体积，c[j] <= i

上面公式代表的是把每一个以c[0],  c[1], c[2]...开头的组合加起来，就是总的组合数。

假设总共n个物品，背包体积为V，时间复杂度为O(V * n)，空间复杂度O(V)，代码如下：