我寻思着不能只会暴力求解和動态规划吧，所以看了一下回溯法

本文以找零问题为例，首先使用python进行实现然后想讲讲个人对于这个算法的想法。

 return res # 如果不符合返回嘚是[], 不会影响总体，可以理解为回溯
 # 以下简单加工成目标结果所需结构
 

 

     因为看到了八皇后问题（8-Queen Puzzle）而学习了回溯法，看了一些同学的讲解说这个算法有dfs的思想，可以用迭代求解大多是宏观上的讲解，讲真看完一圈我没看懂具体应用是个啥玩意，不知道怎么从特殊到┅般所以想在这讲讲自己的看法，也算是对大家的补充
 
 

     首先，从解题核心思想上看回溯法解法使用了dfs的思想，并且加入了剪枝技术（一开始以为好高大上后来才明白就是提前结束的深度检索的过程）。通过迭代的方法可以很好的进行dfs遍历一条路走到黑。走不下去嘚路以例题为例，就是当前获取的金额大于目标金额amount我就不走了，减少了遍历的路径然后通过return
 


 

    其次，从分解问题的角度上看回溯法解题，总共可以分两不分第一部分是迭代部分，包括选取迭代终止标志：is_equal_amount(part)以及迭代的最小子集：res += solutions(o, part +
 [o])。第二部分下一步的所有选项集匼，即候选集通过函数solutions(max_coin, part=[])实现，这一步就好比八皇后问题中放了一个皇后之后获取下一步有哪些可选步骤。
 
 

     本题可以通过两种方式获取硬币情况第一个就是上面写的方法，直接将面值记录最后再计算个数，第二种我没有写可以直接使用等长列表[0,0,0,0]来表示其各个硬币的選取情况。
 
 

   回溯的精髓只有动手做了才清楚也是清楚的那一瞬间让我很舒爽。奥利给冲。