473. 火柴拼正方形

473. 火柴拼正方形

leetcode 链接

解法一：回溯

官方题解

function makesquare(matchsticks) {
  const totalLen = _.sum(matchsticks)
  if (totalLen % 4 !== 0) {
    return false
  }
  matchsticks.sort((a, b) => b - a)

  const edges = Array.from({ length: 4 }).fill(0)
  return dfs(0, matchsticks, edges, Math.floor(totalLen / 4))
}

function dfs(index, matchsticks, edges, len) {
  if (index === matchsticks.length) {
    return true
  }
  for (let i = 0; i < edges.length; i++) {
    edges[i] += matchsticks[index]
    if (edges[i] <= len && dfs(index + 1, matchsticks, edges, len)) {
      return true
    }
    edges[i] -= matchsticks[index]
  }
  return false
}