题目地址：

https://www.lintcode.com/problem/combination-sum-iv/description

给定一个正整数数组$A$，再给定一个正整数$n$，问$n$可以被表达为$A$中的数之和的方案数。两个方案不同当且仅当数字构成不同，或数字构成虽然相同但顺序不同。

这是一种背包问题。设$f[i]$代表$i$可以被表达为$A$中数之和的方案数。那么可以对方案的最后一个数字进行分类，最后一个数字可以是$A[0],A[1],...,A[l_A-1]$，则：$$f[i]=\sum _{i\ge A[j]}f[i-A[j]]$$其中$f[0]=1$。最后只需返回$f[n]$即可。代码如下：

public class Solution { /** * @param nums: an integer array and all positive numbers, no duplicates * @param target: An integer * @return: An integer */ public int backPackVI(int[] nums, int target) { // write your code here int[] dp = new int[target + 1]; dp[0] = 1; for (int i = 1; i <= target; i++) { for (int j = 0; j < nums.length; j++) { if (i >= nums[j]) { dp[i] += dp[i - nums[j]]; } } } return dp[target]; } }

时间复杂度$O(l_{A}n)$，空间$O(n)$。