Leetcode 377 组合总和 Ⅳ

题意理解：

        给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

        题目数据保证答案符合 32 位整数范围。

        这道题目和凑零钱是一样的，需要求使用指定元素（纸币），凑出target(指定金额)有多少种方式。

        此处，元素是可以重复使用的，所以该问题是一个完全背包问题。

解题思路：

        首先了解此题目是一个完全背包问题，所以遍历背包时正序，可以保证元素无限次使用。

        其次，确定题目求得是有多少种方式，而不是重量或最大价值，该题目不是一个纯背包问题。

        由于我们要求组成target得不同方式，1+2  和2+1 被看作是两种方式，所以这里求的是排列数，对于顺序有要求。

        根据之前的总结： 

        求组合数：先物体后背包

        求排列数，先背包后物体

        所以我们选择第二种

1.动态规划解题

 public int combinationSum4(int[] nums, int target) {if(nums.length<=0) return 0;int[] dp=new int[target+1];Arrays.fill(dp,0);dp[0]=1;for(int j=1;j<=target;j++){for(int i=0;i<nums.length;i++){if(nums[i]<=j){dp[j]+=dp[j-nums[i]];}}}return dp[target];}

2.分析

时间复杂度：O(n^2)

空间复杂度：O(n)