火柴拼正方形

题目

题目来源：力扣（LeetCode

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。
输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

输入: [1,1,2,2,2]
输出: true

解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:

输入: [3,3,3,3,4]
输出: false

解释: 不能用所有火柴拼成一个正方形。

思路分析

深度优先搜索 + 回溯

1. 将给定的火柴进行分组，将他们分成四组，每一根火柴恰好属于其中一组。
2. 每一组火柴的长度之和都相同，等于所有火柴长度之和的四分之一。
3. 用深度优先搜索将所有的分组情况都枚举出来，对于每一种情况，判断一下是否满足上面的两种情况。
4. 依次对每一根火柴进行搜索，当搜索出第 i 根火柴的时候，我们可以把它放到四组中的任意一组。
5. 对于每一根火柴的放置方法，我们继续对第 i + 1 根火柴进行递归搜索。
6. 当我们搜索完全部的 N 根火柴后，再判断每一组火柴的长度之和是否都相同。

var makesquare = function(matchsticks) {
  // 判断数组是否存在且长度不为 0
  if (matchsticks === null || matchsticks.length == 0) return false;
  // 火柴的总长度
  let allLen = 0;
  for (let item of matchsticks) {
    allLen += item
  }
  // 判断所有火柴是否可以刚好围成正方形
  if (allLen % 4 !== 0) return false;
  // 正方形的边长
  const sideLen = allLen / 4;
  // 将火柴数组从大到小排序，方便之后优化
  matchsticks.sort((a, b) => b - a);
  // 边长数组，分别保存正方形 4 条边的长度 
  let sideList = new Array(4);
  // 赋初值
  for (let i = 0; i < sideList.length; i++) {
    sideList[i] = 0;
  }
  // index 表示访问到当前火柴的位置
  const dfs = (index) => {
    // 如果火柴都访问完了，判断四条边长是否相等，如果相等，说明是正方形，返回true
    if (index == matchsticks.length) {
      return (
        sideList[0] === sideList[1] && sideList[1] === sideList[2] && sideList[2] === sideList[3]
      )
    }
    // 当前正在处理的火柴
    const targetLen = matchsticks[index];
    // 因为刚才对火柴进行了排序，所以如果有火柴的长度targetLen 大于 我们所计算的边长sideLen，说明所有火柴不能拼接成一个正方形，返回 false
    if (targetLen > sideLen) return false;
    // 到这一步，说明火柴还没访问完
    for (let i = 0; i < 4; i++) {
      // 这一步是回溯，先加上，再去递归判断下一步，如果false，则减去
      if (sideList[i] + targetLen <= sideLen) {
        // 如果当前火柴放到 sideList[i] 这个边上，长度不大于 边长 sideLen，我们就放到这条边上
        sideList[i] += targetLen;
        if (dfs(index + 1)) {
          return true;
        }
        // 如果当前火柴放到 sideList[i] 这个边上，最终不能构成正方形，我们就把他从 sideList[i] 这个边上给移除，然后再试其他的边
        sideList[i] -= targetLen
      }
    }
    //如果不能构成正方形，直接返回false
    return false;
  }
  return dfs(0)
};