面试题，这题目咋做？

[ajsonx]

几个整数组合相加命中某个范围，输出所有的组合方案。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

}

这个时间复杂度肯定不行的。各位大牛有好的解法吗？

[cassyfar]

第一个例子没有 0 0 3 9 或者 6 0 1 等等吗？

[cassyfar]

你那个方法如果是 N 个数组合做不出来吧

这个可以用 DFS 做 把范围内每个整数都搜索下组合

[ajsonx]

@cassyfar 有的，太多了没写出来。

[psychoo]

第一反应是深搜，但咋看咋像背包呢

[ajsonx]

@cassyfar
谢谢回答
我那种做法 无法实现在哪一步？ N 个数 N 层递归不可以吗？
DFS 可以，但时间复杂度没有降低。

[ajsonx]

@psychoo 有道理！谢谢提醒
不过这题求多个解，背包只有最优解。我尝试用 DP 试试

[BiteTheDust]

数据范围？
这个题假如数字可以重复，假设只有 20 个 1，要求范围为[20,20]，那也有整整 C(39,19)=68923264410 种方案数，这样要求输出方案就不实际了。

[zoowii]

粗看只想到两个方法

方法 1，sum 分是否包含某个元素 nums[k[, 变子问题(sum, k-1)和(sum-nums[k], k)。 用 dp 表避免重复计算
方法 2，nums 中各元素构造最小堆，每次弹出一个元素后把弹出元素加上 nums 各元素后的 len(nums)个新元素推入堆中，不断弹出直到找到范围内所有值

[cassyfar]

@ajsonx DFS 时间复杂度是所有组合的数量 这是最小时间复杂度了吧 你还可以做优化 比如 memorization

背包我觉得没差别 因为你最后还是要求出所有组合 而不是组合的数目

你的方法我不是很理解 我以为你是写几个 for loop