这是一个创建于 1718 天前的主题，其中的信息可能已经有所发展或是发生改变。
几个整数组合相加命中某个范围，输出所有的组合方案。int32
Example1:
比如输入 {1,2,3} 范围 [7,9]
可以输出：
（每个 a[i]的个数，最后一个是 sum ）
7 0 0 7
8 0 0 8
9 0 0 9
0 4 0 8
Example2:
输入{1,2,3,4,5} 范围 [30,35]
输出：
30 0 0 0 0 30
0 0 0 0 6 30
最简单的做法：
n = sum /a
m = sum /b
z = sum /c
{
枚举 1 to n
枚举 1 to m
枚举 1 to z
求 sum
}
这个时间复杂度肯定不行的。各位大牛有好的解法吗？
 |
1
cassyfar 2020-03-09 17:27:50 +08:00
第一个例子没有 0 0 3 9 或者 6 0 1 等等吗？
|
|
2
cassyfar 2020-03-09 17:32:54 +08:00
你那个方法如果是 N 个数组合做不出来吧
这个可以用 DFS 做 把范围内每个整数都搜索下组合 |
 |
4
psychoo 2020-03-09 17:38:55 +08:00
第一反应是深搜，但咋看咋像背包呢
|
 |
5
ajsonx OP |
 |
7
BiteTheDust 2020-03-09 18:34:14 +08:00  1
数据范围？
这个题假如数字可以重复，假设只有 20 个 1，要求范围为[20,20]，那也有整整 C(39,19)=68923264410 种方案数，这样要求输出方案就不实际了。 |
 |
8
zoowii 2020-03-09 18:47:12 +08:00 1
粗看只想到两个方法
方法 1，sum 分是否包含某个元素 nums[k[, 变子问题(sum, k-1)和(sum-nums[k], k)。 用 dp 表避免重复计算 方法 2，nums 中各元素构造最小堆，每次弹出一个元素后把弹出元素加上 nums 各元素后的 len(nums)个新元素推入堆中，不断弹出直到找到范围内所有值 |
Select Language