递归方法调用顺序调整一下？

来源：7-7 递归控制_例题列出所有组合

低智商思想家

2019-01-22

是不是应该先做un-select element 0的递归，再做select element 0的递归，这样可以避免arraylist.remove这个O(n)的操作？

写回答

2回答

ccmouse

2019-01-25

是这样的。这里如果反过来做的话，的确可以简单一些还可以省掉remove。

这里先做select一方面比较直观，另一方面演示了我们在“递归的过程中需要把状态复原”这一个非常重要的点。这个例子的确可以通过交换顺序来规避，但更复杂的情况下我们还是必须会要做复原这一步

慕后端8545811

2022-01-25

如果变化一下顺序，最后函数退出之前，是不是也需要remove？保证sideeffect的一致性？

// if we don't choose the first number,

// selected.remove(selected.size()-1);

combination(selected, data.subList(1, data.size()), n);

// if we choose the first number,

selected.add(data.get(0));

combination(selected, data.subList(1, data.size()), n-1);

selected.remove(selected.size()-1);

Google面试官亲授-Java面试新手尊享课

为面试新手量身定制的Java面试尊享课，解锁“鲤鱼跃龙门”的妙招

2853 学习 · 180 问题

相似问题

回答 2

回答 1

回答 3

回答 2

回答 9