估计面试没通过，唉

2020 年 10 月 27 日
 gdw1986
面试前猎头提示我会考递归，妈的，现学真的搞不定啊，题目是 li = [2,3,5,7,9]，输出任意组合，可以重复选，输出所有和是 13 的组合，递归现学现用失败，还是老老实实拿循环写的：
li = [2,3,5,7,9]

def sum13(li):
for i in li:
if i == 13:
print(i)
for j in li:
if i + j == 13:
print(i,j)
for k in li:
if i + j + k== 13:
print(i,j,k)
for l in li:
if i + j + k + l== 13:
print(i,j,k,l)
for o in li:
if i + j + k + l + o == 13:
print(i,j,k,l,o)

我这是面不过了吧？
19490 次点击
所在节点    Python
125 条回复
coderluan
2020 年 10 月 27 日
楼主你被误导了, 这题并不是单纯的递归, 单纯的递归一般现学是能搞定的, 这个实际是动态规划问题, 一般解决动态规划问题会用到递归, 但是绝对不是你会递归就能解决动态规划问题.

然后, 我是面试官肯定不给你过了, 不是你不会动态规划和递归, 而是你连循环都不会写, 按你写的, 5 个数你写 5 个变量判断 5 次 15 行代码, 万一工作中要处理 1 万个数, 不得累死你......
gdw1986
2020 年 10 月 27 日
@coderluan 是的，我觉得也是，哈哈，但是短时间内我实在想不出啥好办法，就硬着头皮写了，总比交白卷强吧
kop1989
2020 年 10 月 27 日
这……lz 你没有 get 到这个题目的关键点。
这个题目的关键不是真的让你筛选出 5 个数中相加得 13 的。

我帮你翻译翻译：怎么能从 x 个数中“最快”的找到相加为 y 的组合？
kkbblzq
2020 年 10 月 27 日
问题是你这循环写的也不怎么样啊，5 重循环亏你写得出来，而且也不对，比如有一个数字是 1，按这题的意思可以选 13 次 1
hikarikun1991
2020 年 10 月 27 日
这是动态规划吧
gdw1986
2020 年 10 月 27 日
@kop1989 但是还有重复的情况，脑壳疼，我只是面个测试要不要要求这么高
gdw1986
2020 年 10 月 27 日
@kkbblzq 好吧，你是对的
gdw1986
2020 年 10 月 27 日
@hikarikun1991 头一次听说这词
oahebky
2020 年 10 月 27 日
这不是 two sum 吗？

（知道 two sum 的朋友，我有没有理解错题意？）

如果中大厂考我 two sum 我会偷笑...


如果大几十人、100 人刚出头的公司考 two sum 就比较无感，最多觉得公司“身体素质”不错。
gdw1986
2020 年 10 月 27 日
@oahebky 还可能 one sum 或者 three sum
wangyzj
2020 年 10 月 27 日
@gdw1986 #6 哈哈哈，面试前刷刷题找找感觉，这玩意一段时间不搞就生疏
不管你搞啥的，先来个算法恶心一下你
wxsm
2020 年 10 月 27 日
DP 头一次听说？哥们你有点水。
vipppppp
2020 年 10 月 27 日
感觉可以多看看生成器，最近工作需要，发现这个东西在动态生成数据很有用。

ii = [2, 3, 5, 7, 9, 1]
target = 13


def solution(score=0):
for i in ii:
if score + i == target:
yield [i]
elif score + i < target:
for rs in solution(score + i):
yield [i] + rs


for s in solution():
print(s)
yhxx
2020 年 10 月 27 日
@oahebky 这是 N sum 吧
比 two sum 还是高了一阶的
MoYi123
2020 年 10 月 27 日
随便写了一个答案,应该是正解

def solution():
____a = [2, 3, 5, 7, 9]
____ret = []
____memo = set()

____def dp(index, acc):
________if (index, tuple(acc)) in memo:
____________return
________else:
____________memo.add((index, tuple(acc)))
________if index == 5:
____________return
________if sum(acc) == 13:
____________ret.append(tuple(acc))
________if sum(acc) >= 13:
____________return
________dp(index + 1, acc[:])
________dp(index, acc[:] + [a[index]])

____dp(0, [])
____return ret
oahebky
2020 年 10 月 27 日
哦...

就是有某一个值可以重复取一直加到 13 就可以...

还还是很难的，一时半会我个人想不出高效的思路。

那应该是面的大厂的样子。
finab
2020 年 10 月 27 日
li 固定为这个数组嘛？ 需要考虑 li 不是 5 个数的情况吧？

递归也可以的，不过性能会比较慢，你这样想


可以先假定有一个函数 叫 comb，可以将数组的数进行组合， 例如输入 [2,3] 就会返回 [[2],[3],[2,3]]
问题就变成了 数组中第一个元素与 comb(数组中其他的元素) 组合

func comb( nums:[Int] ) -> [[Int]] {
if nums.count <= 1 {
//数组中就一个元素，直接原样返回
}
//数组中第一个元素，与 comb(剩下的元素) 返回值 组合起来
for( item in comb(去掉第一个，剩下的元素) ) {
item.insert(nums[0], item.startIndex)
}

//计算最终组合的值，是否等于 13，存在递归之外地方

}
finab
2020 年 10 月 27 日
@finab 刚写完发现能重复选，那上面的写法是错的 囧~
georgetso
2020 年 10 月 27 日
@oahebky 这不是 two sum, [可以重复选]
gdw1986
2020 年 10 月 27 日
@wxsm 哥们只是个测试，确实很水

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://v2ex.ih06.com/t/719057

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX