Facebook Intern 店面2

FB二面
第一个题, 给一个123456789, 找出用加减法组合成一个target的

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

m里, 时间复杂度是O(n2^n)
已gg, 求加面了

第二题应该可以用dp，dp[0] = true, dp[i] |= dp[i - nums[j]], 复杂度O（nk）

所以第二面用backtracking时间应该是2^n的？

鼓頔娜夫 发表于 2016-11-24 09:16
所以第二面用backtracking时间应该是2^n的？

抱歉 *第二题

intern的第二轮不是onsite么？

第一道题求组合个数也只有2^n的解法吗(好像是3^n)？ 第二题是不是combination sum2 那个题呀，我感觉楼主把所有结果存起来不也就是2^n复杂度吗？为什么会n*2^n

楼主第一题和        Expression Add Operators差不多？还有更好的办法吗

第一题写起来很快，结果搞 了10 分钟，结果不对，愣是没看出来一个参数错误。

补充内容 (2017-10-30 11:35):
唉，他家要求一次性过，还是有难度

补充内容 (2017-10-30 11:55):
两题都和target sum差不多。

第二题不要求连续的话复杂度还是无法优化吧？