# 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.

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?```

## 思路一：自顶向下的dp

```    public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length < 1) {
return 0;
}
int[] dp = new int[target + 1];
Arrays.fill(dp, -1);
dp[0] = 1;
return helper(nums, target, dp);
}

private int helper(int[] nums, int target, int[] dp) {
if (dp[target] != -1) {
return dp[target];
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
if (target >= nums[i]) {
res += helper(nums, target - nums[i], dp);
}
}
dp[target] = res;
return res;
}```

## 思路二：自底向上dp

```    public int combinationSum4(int[] nums, int target) {
Arrays.sort(nums);
int[] combinationCount = new int[target+1];

combinationCount[0] = 1;

for(int i = 1 ; i<=target ; i++) {
for(int j = 0 ; j<nums.length && nums[j] <= i ; j++) {
combinationCount[i] += combinationCount[i - nums[j]];
}
}
return combinationCount[target];
}```

0 条评论

• ### leetcode398. Random Pick Index

设计一个数据结构，使得从该数据结构中查询一个数字时，能够以等概率返回该数字所在的任何下标。额外的要求是只要占用O(1)的额外的空间复杂度。

• ### leetcode480. Sliding Window Median

Median is the middle value in an ordered integer list. If the size of the list i...

• ### leetcode363. Max Sum of Rectangle No Larger Than K

现有一个由整数构成的矩阵，问从中找到一个子矩阵，要求该子矩阵中各个元素的和为不超过k的最大值，问子矩阵中元素的和为多少? 注：后面的文章中将使用[左上角顶点坐标...

• ### LintCode 563. 背包问题 V（DP）

给出 n 个物品, 以及一个数组, nums[i] 代表第i个物品的大小, 保证大小均为正数, 正整数 target 表示背包的大小, 找到能填满背包的方案数。

• ### Leetcode 34 Search for a Range

Given a sorted array of integers, find the starting and ending position of a gi...

• ### 多组学整合药物预测如何发6分SCI的？

•IC50 (half maximal inhibitory concentration)最大半抑制浓度,可以用来衡量药物诱导凋亡的能力，即诱导能力越强，该数值...

• ### 苹果的设计中是如何应用 “施奈德曼 黄金准则”的？

苹果公司，作为一家科技巨头，其大量的设计思想非常恰当的反映了Shneiderman（施奈德曼）的8条黄金准则是如何创建出优秀成功的产品的。他们也一直骄傲于自己出...

• ### 全国首张地铁、出租车区块链电子发票在深圳开出

3月18日，全国首张轨道交通区块链电子发票在深圳地铁福田站开出，正式宣告深圳市地铁乘车码上线区块链电子发票功能。即日起，用户使用腾讯旗下智慧交通出行产品乘车码搭...

• ### 【图像分割 】开源 | CVPR2020 | 深度学习框架 | Morpheus天文图像数据像素级分析的深层学习框架

我们提出了一种新的学习框架Morpheus，用于生成天文学像素级的形态学分类。Morpheus框架以深度学习为基础，通过计算机视觉领域的语义分割算法，逐像素地执...