题目
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。
示例 2：
输入：nums = [9], target = 3 输出：0
解题
方法一：动态规划
假设新加的数放在右侧,
比如我们dp[4]中对于112的排序要包含 (1,2,1),(1,1,2),(2,1,1)
举个例子说明一下排序性：
在dp[4]=dp[4-1]+dp[4-2]+dp[4-3]=dp[3]+dp[2]+dp[1];
其中dp[3]=4 为 111，21，12，3
dp[2]=2 为11，2
dp[1]=1 为1
其中211 来源于dp[3]中的21, 我们补个1
121来源于dp[3]中的12，我们补个1
112来源dp[2]中的11,我们补个2
假设我们每次只能把新的数字放在右侧，那么对于容量为3的背包来说，3来源于dp[0]，12来源于dp[1]，21来源于dp[2]。(蓝色代表原有的数字，红色代表新加入的数字)
class Solution { public: int combinationSum4(vector<int>& nums, int target) { vector<int> dp(target+1); dp[0]=1; for(int i=0;i<=target;i++){ for(int j=0;j<nums.size();j++){ if(i-nums[j]>=0&&dp[i]<INT_MAX-dp[i-nums[j]]){ dp[i]+=dp[i-nums[j]]; } } } return dp[target]; } };
java
class Solution { public int combinationSum4(int[] nums, int target) { int[] dp=new int[target+1]; dp[0]=1; for(int i=0;i<=target;i++){ for(int j=0;j<nums.length;j++){ if(i-nums[j]>=0){ dp[i]+=dp[i-nums[j]]; } } } return dp[target]; } }
总结：
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
如果求01背包问题，容量从末尾开始遍历。
如果求完全背包问题，容量从头开始遍历。
