中等

问题描述

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

如果你能使这个正方形，则返回 true ，否则返回 false 。

示例 1:

输入: matchsticks = [1,1,2,2,2]
输出: true
解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:

输入: matchsticks = [3,3,3,3,4]
输出: false
解释: 不能用所有火柴拼成一个正方形。

提示:

• 1 <= matchsticks.length <= 15
• 1 <= matchsticks[i] <= 108

回溯 + 剪枝

首先计算所有火柴的总长度 $Sum$， 如果 $Sum$ 不是 $4$ 的倍数，那么肯定不能拼成正方形，返回 $false$。

直接暴搜的话，时间复杂度为 $O(4^n)$，需要考虑 剪枝优化。

1. 从长到短枚举火柴长度，因为先选取较长的火柴，后面可以选择的空间会更少，从而减少查询次数。
2. 对于当前边，如果加入第一根火柴时的递归就失败，可以进行剪枝，因为每根火柴棒必须 使用一次，买条边都是从长度 $0$ 开始的，这条边失败，后面的边必然失败。
3. 同理，对于加入最后一根火柴时的递归失败，也可以进行剪枝。
4. 对于当前边，如果加入长度为 $x$ 的火柴时，递归失败，那么，后面与 $x$ 长度相同的火柴可以直接跳过。
5. 当三条边已经满足要求时，第四条边必然满足要求。

/**
 * @param {number[]} matchsticks
 * @return {boolean}
 */
var makesquare = function (matchsticks) {
  if (matchsticks.length < 4) return false
  const sum = matchsticks.reduce((sum, cur) => sum + cur)
  if (sum % 4 !== 0) return false
  const target = sum / 4
  matchsticks.sort((a, b) => b - a)
  if (matchsticks[0] > target) return false
  const visited = new Array(matchsticks.length).fill(false)
  const backtrack = (len, edge) => {
    if (len === target) {
      len = 0
      edge += 1
    }
    if (edge === 4) return true
    for (let i = 0; i < matchsticks.length; i++) {
      if (!visited[i] && len + matchsticks[i] <= target) {
        visited[i] = true
        if (backtrack(len + matchsticks[i], edge)) return true
        visited[i] = false
        if (!len) return false
        if (len + matchsticks[i] == target) return false
        while (i + 1 < matchsticks.length && matchsticks[i] === matchsticks[i + 1]) i++
      }
    }
    return false
  }
  return backtrack(0, 1)
}

• 时间复杂度：$O(4^n)$
• 空间复杂度：$O(n)$

状态压缩 + 动态规划

前期的预处理是一样的，不同的是动态规划的过程。

使用状态 $s$ 记录哪些火柴已经被选取（$s$ 的第 $k$ 位为 $1$ 表示第 $k$ 根火柴已经被选，因此有 $2^n$ 个状态），$dp[s]$ 表示当前未放满的边的长度。

• 当 $s = 0$ 时，所有火柴都未被选取， $dp[0] = 0$
• 当 $s > 0$ 时，记每条边长为 $len$ 当前状态为$s$($s$ 的第 $k$ 位为 $1$)，第 $k$ 根火柴未被选取的状态为 $s'$。若 $dp[s'] \geq 0$ 且满足 $dp[s'] + matchsticks[k] \leq len$，那么 $dp[s] = (dp[s'] + matchsticks[k]) \; \text {mod} \; len$，这里取余的意思是当前一条边放满时 $dp[s'] + matchsticks[k] = len$，那么 $len \; \text {mod} \; len = 0$，下一条未放满的边的长度为 $0$。若不满足条件，则 $\text {dp}[s] = -1$，表示状态 $s$ 对应的火柴选取方式不可能按上述规则放入正方形的边。

最终，当所有火柴都已经被放入时($s = 2^n - 1$)，如果 $dp[2^n - 1] = 0$，说明可以拼成正方形，否则不可以拼成正方形。

/**
 * @param {number[]} matchsticks
 * @return {boolean}
 */
var makesquare = function (matchsticks) {
  if (matchsticks.length < 4) return false
  const sum = matchsticks.reduce((sum, cur) => sum + cur)
  if (sum % 4 !== 0) return false
  const len = sum / 4
  const n = matchsticks.length
  const N = 1 << n
  const dp = new Array(N).fill(-1)
  dp[0] = 0
  for (let s = 0; s < N; s++) {
    for (let k = 0; k < n; k++) {
      // 第 k 根火柴选中
      if ((s >> k) & 1) {
        const s1 = s & ~(1 << k)
        if (dp[s1] >= 0 && dp[s1] + matchsticks[k] <= len) {
          dp[s] = (dp[s1] + matchsticks[k]) % len
          break
        }
      }
    }
  }
  return dp[N - 1] === 0
}

• 时间复杂度：$O(n \times 2^n)$
• 空间复杂度：$O(2^n)$