IXL学习电面面经，两个回溯题

刚刚做完的。
上来先来一个 二和 探底
秒杀后直接搬上来n和(利扣39/40)，而且只需要求一个解。有点蒙，因为只要求一个解，想

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

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

50分钟三题，两个backtracking。。。。求onsite啊

xiaozhuxiaozhu 发表于 2017-6-28 05:20

空回复是怎么回事。。。

cgxy1991 发表于 2017-6-28 05:24
空回复是怎么回事。。。

论坛可能出错了。
combination sum如果只找1个解，需要在backtracking上进行pruning。并且，不需要pass进原来的list<list<integer>>

一般有几种方法，思路基本都一样：
1: 把原来的helper function返程返回true, false， 如果找到一个解，直接在dfs的路径上返回。
2: pass进去一个extra global variable， 用来代表是否找到第1个解，如果找到直接set variable = true, 然后dfs返回。
3: 这个只需要在原来的code上面加if statement, if(list.size())==1) return；    list是存放解的list， 这个代码，加在每次要进行dfs的前面，如果我已经找到解了，说明，我不需要继续dfs了，直接返回。

猜下这题的考点， backtracking，
他需要只求1个解，这个感觉有2两种情况
1 ： 他是想考dfs + pruning， lz没有做pruning的部分／
2 ： 他是想把原题变简单，所有解，需要pass 进去list<list<integer>> 和list<integer>， 1个解，只需要一个list<integer>。
希望他是第2种情况。
祝好运。

xiaozhuxiaozhu 发表于 2017-6-28 05:48
论坛可能出错了。
combination sum如果只找1个解，需要在backtracking上进行pruning。并且，不需要pass ...

可能确实是这样。不过我既然提出了backtracking，那就符合他的要求了吧。。。