02 | 暴力递归：当贪心失效了怎么办？

这里给出一种解决括号生成的解法，用C++语言描述，供大家参考： class Solution { public: vector<string> generateParenthesis(int n) { std::vector<string> v; backtrace("", 0, 0, n, v); return v; } void backtrace(std::string cur, int left, int right, int n, std::vector<string>& v) { if (left + right == 2*n) { v.push_back(cur); return; } if (left < n) backtrace(cur + "(", left+1, right, n, v); if (right < left) backtrace(cur + ")", left, right+1, n, v); } };

第二讲暴力递归 要得到整体最优解需要找出所有符合的情况，选出其中一个最优组合，符合整体最优。 全部跑出结果再判断，这会浪费很多空间来存储结果组合 所以在递归过程中，进入最内层返回得到结果时舍弃不符合的，保留更符合的，直到退回递归的顶层，就可以得到唯一的结果。 递归的方法是为了保存之前的状态，回退时使用，这其实就是栈的数据结构，可以改为非递归的方式。 使用递归，失败了可以回退，这种回退找正确答案的思路就是回溯，每次都找到树型结构的底部就叫深度优先的思路。 这种全部结果都遍历出来，取最优解的做法是暴力递归，性能差难以调试，效率低，可读性差，可以使用剪枝优化。 贪心算法是动态规划的源头，但是他局限于求局部最优解，但是用到暴力递归里，就可以达到剪枝的效果。 第二种优化策略，重叠子问题，余额相同的时候搜索路径是完全一致。所以可以把大问题拆分为小问题，这就是备忘录和动态规划的基础。

第一种思路是仿照贪心算法，从整个搜索策略上来调整。也就是说，你要考虑这个问题的性质，即面值大的硬币用得足够多，那么这个组合的硬币总数肯定就最小。 这句话我想了下，不是很同意这个说法。比如 硬币 10 7 1，金额 14。按照上面所说 那么他得到的解 10， 1， 1， 1， 1，这个时候就结束了。但其实最有解是7,7。老师您，上一课的代码只能获得一个解，并不能获取最优解

换了vector之后代码可读性好了好多，上一篇那个数组，看了好久。。。。。。

参照贪心算法的优化，起不到优化的作用吧，前面就有评论也说过，需要对比所有的结果才知道是不是最优，除非只是想得到一个结果，而这个结果要尽可能的好。 或者是基于前面得到的解作为其它递归的剪枝条件之一

JavaScript: ``` var generateParenthesis = function (n) { const ret = [] const _helper = (left, right, parenthesi) => { if (left === 0 && right === 0) { ret.push(parenthesi) } if (left > 0) { _helper(left - 1, right, parenthesi + '(') } if (right > left) { _helper(left, right - 1, parenthesi + ')') } } _helper(n, n, '') return ret }; ```

这里要说明一下Java和C++的区别： // List<Integer> initialCounts = new ArrayList<>(2); // Collections.fill(initialCounts, 0); List<Integer> initialCounts = Arrays.stream(new int[values.length]) .boxed().collect(Collectors.toList()); 初始化之后的initialCounts依然是0，直接访问修改会发生越界错误的，所以采用lamda的方式初始化initialCounts You're confusing the size of the array list with its capacity: the size is the number of elements in the list; the capacity is how many elements the list can potentially accommodate without reallocating its internal structures. When you call new ArrayList<Integer>(10), you are setting the list's initial capacity, not its size. In other words, when constructed in this manner, the array list starts its life empty. One way to add ten elements to the array list is by using a loop: initialCounts.add(0);

```java public List<String> genParenthesis(int n) { List<String> res = new ArrayList<>(); dfs(0,0,n,"",res); return res; } private void dfs(int l,int r,int n,String s,List<String> res){ if(l == r && l == n){ if(check(s)){ res.add(s); } return; } if(l < n){ dfs(l+1,r,n,s + "(",res); } if(r < n){ dfs(l,r+1,n,s + ")",res); } } private boolean check(String s){ Stack<Character> stack = new Stack<>(); for(char c : s.toCharArray()){ if(c == '(') { stack.push(c); continue; } if(stack.isEmpty()){ return false; } stack.pop(); } return stack.isEmpty(); } ```

# 暴力递归 python实现 # 枚举出满足条件的局部最优解，进而求得全局最优解 # 枚举的方法就是递归 # 问题描述：硬币组合，给出硬币面值，计算特定值的最小硬币数量 # 如：面值：[3, 5] 特定值：11 返回：3 import sys def get_min_counts_helper(total, values): # 如果余额为 0，说明当前组合成立，将组合加入到待选数组中 if total == 0: return 0 # 面值个数 value_length = len(values) # 返回最小硬币数量 min_count = sys.maxsize for i in range(value_length): # 如果当前面值大于硬币总额，那么跳过 if values[i] > total: continue # 特定值减去当前面币值后余额 rest = total - values[i] rest_count = get_min_counts_helper(rest, values) # 如果返回 -1， 说明组合不可信，跳过 if rest_count == -1: continue # 硬币数量增加一枚 total_count = rest_count + 1 # 保留最小总额 min_count = total_count if total_count < min_count else min_count # 如果没有可用组合，返回 -1 if min_count == sys.maxsize: return -1 return min_count def get_min_count_of_coins(): values = [3, 5] # 硬币面值数组 total = 11 # 特定值 return get_min_counts_helper(total, values) get_min_count_of_coins()

关键代码解释得不是很清楚，看文本都懂，看这个代码真的懵了