首页 > 代码库 > [leetcode-377-Combination Sum IV]
[leetcode-377-Combination Sum IV]
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
Example:
nums = [1, 2, 3] target = 4 The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations. Therefore the output is 7.
Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?
思路:
参考自:http://www.cnblogs.com/grandyang/p/5705750.html
这道题的真正解法应该是用DP来做,解题思想有点像之前爬梯子的那道题Climbing Stairs,我们需要一个一维数组dp,其中dp[i]表示目标数为i的解的个数,然后我们从1遍历到target,对于每一个数i,遍历nums数组,如果i>=x, dp[i] += dp[i - x]。这个也很好理解,比如说对于[1,2,3] 4,这个例子,当我们在计算dp[3]的时候,3可以拆分为1+x,而x即为dp[2],3也可以拆分为2+x,此时x为dp[1],3同样可以拆为3+x,此时x为dp[0],我们把所有的情况加起来就是组成3的所有情况了,参见代码如下:
int combinationSum4(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<int>dp(target+1,0); dp[0] = 1; for (int i = 1; i <= target;i++) { for (int a : nums) { if (i<a)break;//a排序后只能越来越大 i>=a才有意义 否则提前结束内部循环 dp[i] += dp[i - a]; } } return dp[target]; }
[leetcode-377-Combination Sum IV]
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。