[2022-06-01]473. 火柴拼正方形👋位运算👋数组👋动态规划👋回溯👋状态压缩

[webVueBlog]

题目链接: https://leetcode-cn.com/problems/matchsticks-to-square

难度: Medium
标签: 位运算 数组 动态规划 回溯 状态压缩

[webVueBlog]

/*
 * @lc app=leetcode.cn id=473 lang=javascript
 *
 * [473] 火柴拼正方形
 */

// @lc code=start
/**
 * @param {number[]} matchsticks
 * @return {boolean}
 (380 ms)
 */
 var makesquare = function(matchsticks) {
  const totalNum = matchsticks.reduce((cur, item) => cur + item, 0);
  if(totalNum % 4 !== 0) return false
  matchsticks.sort((a, b) => b - a);
  // 存储每一边的状态
  const  edges = new Array(4).fill(0),
  len = ~~(totalNum / 4);
  let dfs = (start) => {
   if(start === matchsticks.length) {
    return true;
   } else {
    for(let i = 0; i < edges.length; i++) {
     edges[i] += matchsticks[start];
     if(edges[i] <= len && dfs(start + 1)) {
      return true;
     }
     edges[i] -= matchsticks[start];
    }
    return false;
   }
  }
  return dfs(0);
};
// @lc code=end