Python语言目前是最火的语言之一，语法简单，功能强大，最新的TIOBE已公布2020年6月的编程语言排行榜，Python已经连续多个月都在前三甲了，非常火爆！
现在学习Python的同学越来越多，面试的环节，很多面试官让你任选语言进行编程。Python因为简单，很多小伙伴愿意用Python进行答题。最近我们的一个粉丝交流群，有一位同学跟我分享了他面试的经历。小李学了Python大概有2年多了，他跟我讲了前段时间面试某杭州大厂的一道面试题，注意是面试题，不是笔试卷。
现场让你手写代码，压力山大啊～～也许是因为紧张的原因，也许是因为自己算法基础底子不深的原因，反正现场憋了很久，没有憋出来。到底是什么样的一个算法题呢，一起来看一下。
面试的题目
题目：
假设你手上有面值1块，2块，5块各若干张纸币，你现在需要支付给商家6元钱，请问你有多少种组合，列出每一种组合？
要求：
1).在白板上手写代码或者直接在电脑上写
2).分析你的算法，如何优化
3).对搜索的结果进行分析
看起来这个问题似乎很简单，就是一个空间组合搜索，然后加起来的面值为6即可，但是现场面试给你思考的时间，不会超过1分钟。小李当时就心里咯噔一下，leetcode的题目少刷了，其实面试之前也准备了，刷了一些算法题，但是还是手生了一些。
大家可以思考一下，如果是你的话，你先不看下面的答案，现场手写能写出来吗？
思路：
这个题目其实网上也很多类似的，就是钞票的选取方案而已，一般的解法都是递归。递归只要设计出口即可。如果我们的方案等于6元即退出，如果超过了6元就放弃，如果不足6元就继续添加更多的钞票即可。
bills是钞票面额的列表(假如为[1,2,5]),然后target是目标值(假如为6),然后填入一个空列表的方案 solution
-
如果总金额等于target就打印solution;
-
如果大于总金额就放弃；
-
上面两种都不满足的时候，就是金额不够的情况，进行一个递归搜索，这里等于设计一个容器ways(用来存放方案，直接复制solution 列表)，然后不断的加入一张钞票进行递归；
如果能现场写出来这个代码，并且运行成功，其实还是蛮厉害的，走到这一步，相信至少能拿到及格的分数了。但是面试官会进行第二次的提问，你觉得这个算法哪里有问题，怎么解决？
确实这个里面有很多重复的方案，比如[1,1,1,1,2]和[1,1,1,2,1]就是完全重复的，我们需要取重复。
二次优化
很明显上面的搜索是大而全的，就是有很多浪费的空间，如果我们的搜索的样本很大的话，就会有很多浪费的空间，这样的效率肯定是低的，如何优化呢？
有的同学说可以保存结果然后进行取重复，但是这样要等整个的结果出来才行；有没有办法在搜索空间算法上动手脚呢？
我们来看一些优化后的代码：
是不是过滤了很多重复的方案，我们在搜索的方案里面加一个新参数bigger，就是当前的已经生成的最高的面额，在搜索的过程中，我们只能append那些大于等于已经加入的最高的面额钞票，低的我们就不卖了。
当然还有其他的解决办法，其实如果回答出这个参数，相信会给面试官加分不少，说明在工作的时候，并不是一个只知道完成任务的，还是一个喜欢勤思考会优化代码的人。其实面试的时候回答出这一步，已经是可以拿到良好分了。
如何对搜索结果进行分析
上面的结果都是在通过print打印在内存里面，如果我们需要对整个的搜索的空间进行进一步的处理，比如我们有100种方案，我们需要保存到文件中或者数据库里面进一步的分析，如果把递归的结果提取出来呢？
第一种，简单粗暴：
我们直接用全局变量，在整个函数的外部加一个out=[]，来存储所有的组合：
第二种,优雅的方式
全局变量固然简单，但是在生产的环境的项目里面，这肯定不是最佳的解法。最好的方法还是在函数内自己存储，然后我们只要在调用的时候获取即可。这里我们用Python里面的生成器yield来搞定。
通过yield来缓存递归过程的结果，是不是非常优雅。这个时候我们对所有的组合可以进行分析，比如我想找到用钞票最少的组合，就可以这样：
小编说两句：
其实整个这道面试题，如果是放在笔试题里面，相信大部分的同学都可以答出来，难度其实并不大。但是在面试的环节，就会难很多，一个紧张，二个思考的时间非常短，需要平时有深厚的积累！
建议参加大厂的面试，多多少少都要准备一下尤其是算法。一定要多刷一些leetcode的题目，不要照搬照套，一定要理解并且把代码学到肚子里去，实在不行，先把代码思路背下来，这样有备无患，毕竟临阵磨枪，不快也光！好了，希望今天的文章对大家有帮助。
<pre><p><span style="font-size: 15px;color: rgb(255, 41, 65);"><strong>近期原创热门：</strong></span></p><ul class="list-paddingleft-2"><li style="font-size: 15px;"><p style="line-height: 1.75em;">避坑指南！Python里面的这九个坑<br /></p></li><li style="font-size: 15px;"><p style="line-height: 1.75em;">再见，付费录屏软件！我用70行Python代码打造免费版！<br /></p></li><li style="font-size: 15px;"><p style="line-height: 1.75em;">真香！一行Python代码，帮你制作小姐姐的表情包<br /></p></li><li style="font-size: 15px;"><p style="line-height: 1.75em;">学Python还是Java, 7张漫画带你全面分析<br /></p></li><li style="font-size: 15px;"><p style="line-height: 1.75em;"><span style="text-decoration: underline;">一个炫酷的Python库，让你的终端输出方式，逼格秒变高！</span></p></li></ul>
由菜鸟学Python原班人马打造的【程序员GitHub】开始啦！专注于分享GitHub上有趣的资源包括，Python，Java，Go语言，前端学习等优质的学习资源，分享程序员圈的新鲜趣事，热门干货，职场感悟。
<section data-mpa-template="t" mpa-from-tpl="t"><section data-id="94086" data-color="#276ca3" data-tools="135编辑器" mpa-from-tpl="t"><section style="text-align: right;"><section mpa-from-tpl="t" style="display: inline-block;"><pre style="letter-spacing: 0.544px;line-height: inherit;"><pre data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-style="letter-spacing: 0.544px; background-color: rgb(255, 255, 255); text-align: center; color: rgba(230, 230, 230, 0.9); font-size: 16px; line-height: 25.6px; overflow-wrap: break-word !important;" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgba(230, 230, 230, 0.9)" data-darkmode-original-color-15882396318564="rgba(230, 230, 230, 0.9)" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgba(230, 230, 230, 0.9)" data-darkmode-original-color-15900529136199="rgba(230, 230, 230, 0.9)" class="js_darkmode__5" style="letter-spacing: 0.544px;text-align: center;color: rgba(230, 230, 230, 0.9);line-height: 25.6px;"><section class="js_darkmode__7"><section data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(230, 230, 230)" data-darkmode-original-color-15860613985508="rgb(0, 0, 0)" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(230, 230, 230)" data-darkmode-original-color-15870356070738="rgb(0, 0, 0)" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(230, 230, 230)" data-darkmode-original-color-15870356071023="rgb(0, 0, 0)" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(230, 230, 230)" data-darkmode-original-color-15882384789136="rgb(0, 0, 0)" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(230, 230, 230)" data-darkmode-original-color-15882396318564="rgb(0, 0, 0)" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(230, 230, 230)" data-darkmode-original-color-15900529136199="rgb(0, 0, 0)" style="display: inline-block;clear: both;"><section data-tools="135编辑器" data-id="91842" data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(230, 230, 230)" data-darkmode-original-color-15860613985508="rgb(0, 0, 0)" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(230, 230, 230)" data-darkmode-original-color-15870356070738="rgb(0, 0, 0)" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(230, 230, 230)" data-darkmode-original-color-15870356071023="rgb(0, 0, 0)" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(230, 230, 230)" data-darkmode-original-color-15882384789136="rgb(0, 0, 0)" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(230, 230, 230)" data-darkmode-original-color-15882396318564="rgb(0, 0, 0)" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(230, 230, 230)" data-darkmode-original-color-15900529136199="rgb(0, 0, 0)" style="letter-spacing: 0.544px;border-width: 0px;border-style: none;border-color: initial;"><section data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(230, 230, 230)" data-darkmode-original-color-15860613985508="rgb(0, 0, 0)" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(230, 230, 230)" data-darkmode-original-color-15870356070738="rgb(0, 0, 0)" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(230, 230, 230)" data-darkmode-original-color-15870356071023="rgb(0, 0, 0)" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(230, 230, 230)" data-darkmode-original-color-15882384789136="rgb(0, 0, 0)" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(230, 230, 230)" data-darkmode-original-color-15882396318564="rgb(0, 0, 0)" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(230, 230, 230)" data-darkmode-original-color-15900529136199="rgb(0, 0, 0)" style="display: inline-block;clear: both;"><section data-brushtype="text" data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(230, 230, 230)" data-darkmode-original-color-15860613985508="rgb(0, 0, 0)" data-darkmode-bgimage-15860613985508="1" data-style="padding: 18px 15px 20px 10px; color: rgb(86, 146, 214); text-align: center; letter-spacing: 1.5px; background-image: url('https://www.zkxjob.com/wp-content/uploads/2022/05/wxsync-2022-05-a2a8a5e1e58f30392066a170034ee027.png'); background-size: 100% 100%; background-repeat: no-repeat; overflow-wrap: break-word !important;" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(230, 230, 230)" data-darkmode-original-color-15870356070738="rgb(0, 0, 0)" data-darkmode-bgimage-15870356070738="1" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(230, 230, 230)" data-darkmode-original-color-15870356071023="rgb(0, 0, 0)" data-darkmode-bgimage-15870356071023="1" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(230, 230, 230)" data-darkmode-original-color-15882384789136="rgb(0, 0, 0)" data-darkmode-bgimage-15882384789136="1" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(230, 230, 230)" data-darkmode-original-color-15882396318564="rgb(0, 0, 0)" data-darkmode-bgimage-15882396318564="1" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(230, 230, 230)" data-darkmode-original-color-15900529136199="rgb(0, 0, 0)" data-darkmode-bgimage-15900529136199="1" class="js_darkmode__bg__0 js_darkmode__8" style="padding: 18px 15px 20px 10px;background-size: 100% 100%;background-image: url('https://www.zkxjob.com/wp-content/uploads/2022/05/wxsync-2022-05-a2a8a5e1e58f30392066a170034ee027.png');color: rgb(86, 146, 214);letter-spacing: 1.5px;background-repeat: no-repeat;"><section data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(230, 230, 230)" data-darkmode-original-color-15860613985508="rgb(0, 0, 0)" data-darkmode-bgimage-15860613985508="1" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(230, 230, 230)" data-darkmode-original-color-15870356070738="rgb(0, 0, 0)" data-darkmode-bgimage-15870356070738="1" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(230, 230, 230)" data-darkmode-original-color-15870356071023="rgb(0, 0, 0)" data-darkmode-bgimage-15870356071023="1" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(230, 230, 230)" data-darkmode-original-color-15882384789136="rgb(0, 0, 0)" data-darkmode-bgimage-15882384789136="1" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(230, 230, 230)" data-darkmode-original-color-15882396318564="rgb(0, 0, 0)" data-darkmode-bgimage-15882396318564="1" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(230, 230, 230)" data-darkmode-original-color-15900529136199="rgb(0, 0, 0)" data-darkmode-bgimage-15900529136199="1" style="display: flex;justify-content: center;align-items: center;"><section data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(230, 230, 230)" data-darkmode-original-color-15860613985508="rgb(0, 0, 0)" data-darkmode-bgimage-15860613985508="1" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(230, 230, 230)" data-darkmode-original-color-15870356070738="rgb(0, 0, 0)" data-darkmode-bgimage-15870356070738="1" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(230, 230, 230)" data-darkmode-original-color-15870356071023="rgb(0, 0, 0)" data-darkmode-bgimage-15870356071023="1" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(230, 230, 230)" data-darkmode-original-color-15882384789136="rgb(0, 0, 0)" data-darkmode-bgimage-15882384789136="1" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(230, 230, 230)" data-darkmode-original-color-15882396318564="rgb(0, 0, 0)" data-darkmode-bgimage-15882396318564="1" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(230, 230, 230)" data-darkmode-original-color-15900529136199="rgb(0, 0, 0)" data-darkmode-bgimage-15900529136199="1" style="margin-left: 2px;word-spacing: 1px;width: 20px;"></section><section data-brushtype="text" data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(51, 51, 51)" data-darkmode-original-color-15860613985508="rgb(51, 51, 51)" data-darkmode-bgimage-15860613985508="1" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(51, 51, 51)" data-darkmode-original-color-15870356070738="rgb(51, 51, 51)" data-darkmode-bgimage-15870356070738="1" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(51, 51, 51)" data-darkmode-original-color-15870356071023="rgb(51, 51, 51)" data-darkmode-bgimage-15870356071023="1" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(51, 51, 51)" data-darkmode-original-color-15882384789136="rgb(51, 51, 51)" data-darkmode-bgimage-15882384789136="1" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(51, 51, 51)" data-darkmode-original-color-15882396318564="rgb(51, 51, 51)" data-darkmode-bgimage-15882396318564="1" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(51, 51, 51)" data-darkmode-original-color-15900529136199="rgb(51, 51, 51)" data-darkmode-bgimage-15900529136199="1" style="word-spacing: 1px;font-size: 14px;color: rgb(51, 51, 51);text-align: right;"><span data-darkmode-bgcolor-15860613985508="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15860613985508="rgb(255, 255, 255)" data-darkmode-color-15860613985508="rgb(51, 51, 51)" data-darkmode-original-color-15860613985508="rgb(51, 51, 51)" data-darkmode-bgimage-15860613985508="1" data-darkmode-bgcolor-15870356070738="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356070738="rgb(255, 255, 255)" data-darkmode-color-15870356070738="rgb(51, 51, 51)" data-darkmode-original-color-15870356070738="rgb(51, 51, 51)" data-darkmode-bgimage-15870356070738="1" data-darkmode-bgcolor-15870356071023="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15870356071023="rgb(255, 255, 255)" data-darkmode-color-15870356071023="rgb(51, 51, 51)" data-darkmode-original-color-15870356071023="rgb(51, 51, 51)" data-darkmode-bgimage-15870356071023="1" data-darkmode-bgcolor-15882384789136="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882384789136="rgb(255, 255, 255)" data-darkmode-color-15882384789136="rgb(51, 51, 51)" data-darkmode-original-color-15882384789136="rgb(51, 51, 51)" data-darkmode-bgimage-15882384789136="1" data-darkmode-bgcolor-15882396318564="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15882396318564="rgb(255, 255, 255)" data-darkmode-color-15882396318564="rgb(51, 51, 51)" data-darkmode-original-color-15882396318564="rgb(51, 51, 51)" data-darkmode-bgimage-15882396318564="1" data-darkmode-bgcolor-15900529136199="rgb(36, 36, 36)" data-darkmode-original-bgcolor-15900529136199="rgb(255, 255, 255)" data-darkmode-color-15900529136199="rgb(51, 51, 51)" data-darkmode-original-color-15900529136199="rgb(51, 51, 51)" data-darkmode-bgimage-15900529136199="1" style="font-family: 楷体, 楷体_GB2312, SimKai;">点的“在看”，否则就看不到我了555</span></section><p><br /></p></section></section></section></section></section></section>本篇文章来源于: 菜鸟学Python
本文为原创文章，版权归知行编程网所有，欢迎分享本文，转载请保留出处！
内容反馈