520，回溯算法解火柴拼正方形
Only those that risk going too far can possibly know how far they can go.
只有勇于承担风险，敢于走出去的人，才会明白他们到底能走多远。
问题描述
还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。
示例 1:
输入: [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例 2:
输入: [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。
注意:
给定的火柴长度和在 0 到 10^9之间。
火柴数组的长度不超过15。
回溯算法解决
这题是让所有的火柴能不能拼接成一个正方形，不能折断火柴，并且所有的火柴都要用到。
首先先求出所有火柴的长度，然后判断是否是4的倍数，如果不是，直接返回false，表示不能拼接成正方形，如果是4的倍数然后在往下走。
把每一根火柴都尝试往4条边上放，如果最终能构成正方形，直接返回true。看一下视频
这就是回溯算法，他不断的尝试，一旦成功也就成功了。如果不成功，在回到上一步继续尝试，其实他有一个经典的模板
1private void backtrack("原始参数") {
2 //终止条件(递归必须要有终止条件)
3 if ("终止条件") {
4 //一些逻辑操作（可有可无，视情况而定）
5 return;
6 }
7
8 for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
9 //一些逻辑操作（可有可无，视情况而定）
10
11 //做出选择
12
13 //递归
14 backtrack("新的参数");
15 //一些逻辑操作（可有可无，视情况而定）
16
17 //撤销选择
18 }
19}
我们来看下最终代码
1public boolean makesquare(int[] nums) {
2 int total = 0;
3 //统计所有火柴的长度
4 for (int num : nums) {
5 total += num;
6 }
7 //如果所有火柴的长度不是4的倍数，直接返回false
8 if (total == 0 || (total & 3) != 0)
9 return false;
10 //回溯
11 return backtrack(nums, 0, total >> 2, new int[4]);
12}
13
14//index表示访问到当前火柴的位置，target表示正方形的边长，size是长度为4的数组，
15//分别保存正方形4个边的长度
16private boolean backtrack(int[] nums, int index, int target, int[] size) {
17 if (index == nums.length) {
18 //如果火柴都访问完了，并且size的4个边的长度都相等，说明是正方形，直接返回true，
19 //否则返回false
20 if (size[0] == size[1] && size[1] == size[2] && size[2] == size[3])
21 return true;
22 return false;
23 }
24 //到这一步说明火柴还没访问完
25 for (int i = 0; i < size.length; i++) {
26 //如果把当前火柴放到size[i]这个边上，他的长度大于target，我们直接跳过
27 if (size[i] + nums[index] > target)
28 continue;
29 //如果当前火柴放到size[i]这个边上，长度不大于target，我们就放上面
30 size[i] += nums[index];
31 //然后在放下一个火柴，如果最终能变成正方形，直接返回true
32 if (backtrack(nums, index + 1, target, size))
33 return true;
34 //如果当前火柴放到size[i]这个边上，最终不能构成正方形，我们就把他从
35 //size[i]这个边上给移除，然后在试其他的边
36 size[i] -= nums[index];
37 }
38 //如果不能构成正方形，直接返回false
39 return false;
40}
代码优化
如果数组前面数组比较小，这会导致递归的比较深，所以我们可以先对数组进行排序，从大的开始递归，代码如下
1public boolean makesquare(int[] nums) {
2 int total = 0;
3 //统计所有火柴的长度
4 for (int num : nums) {
5 total += num;
6 }
7 //如果所有火柴的长度不是4的倍数，直接返回false
8 if (total == 0 || (total & 3) != 0)
9 return false;
10 //先排序
11 Arrays.sort(nums);
12 //回溯，从最长的火柴开始
13 return backtrack(nums, nums.length - 1, total >> 2, new int[4]);
14}
15
16//index表示访问到当前火柴的位置，target表示正方形的边长，size是长度为4的数组，
17//分别保存正方形4个边的长度
18private boolean backtrack(int[] nums, int index, int target, int[] size) {
19 if (index == -1) {
20 //如果火柴都访问完了，并且size的4个边的长度都相等，说明是正方形，直接返回true，
21 //否则返回false
22 if (size[0] == size[1] && size[1] == size[2] && size[2] == size[3])
23 return true;
24 return false;
25 }
26 //到这一步说明火柴还没访问完
27 for (int i = 0; i < size.length; i++) {
28 //如果把当前火柴放到size[i]这个边上，他的长度大于target，我们直接跳过。或者
29 // size[i] == size[i - 1]即上一个分支的值和当前分支的一样，上一个分支没有成功，
30 //说明这个分支也不会成功，直接跳过即可。
31 if (size[i] + nums[index] > target || (i > 0 && size[i] == size[i - 1]))
32 continue;
33 //如果当前火柴放到size[i]这个边上，长度不大于target，我们就放上面
34 size[i] += nums[index];
35 //然后在放下一个火柴，如果最终能变成正方形，直接返回true
36 if (backtrack(nums, index - 1, target, size))
37 return true;
38 //如果当前火柴放到size[i]这个边上，最终不能构成正方形，我们就把他从
39 //size[i]这个边上给移除，然后在试其他的边
40 size[i] -= nums[index];
41 }
42 //如果不能构成正方形，直接返回false
43 return false;
44}
总结
回溯算法还是有一个经典模板的，他的原理就是不断尝试的过程，一旦尝试失败就会回到上一步继续尝试，上面代码中都有详细的注释，很容易理解。
截止到目前我已经写了500多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有800多页，大家可以在公众号中回复关键字“pdf”即可获取下载链接。