473.火柴拼正方形

链接：473.火柴拼正方形
难度：Medium
标签：位运算、数组、动态规划、回溯、状态压缩
简介：输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

题解 1 - typescript

• 编辑时间：2022-06-01
• 执行用时：224ms
• 内存消耗：9.5MB
• 编程语言：typescript
• 解法介绍：dfs。

class Solution {
   public:
    bool makesquare(vector<int> &matchsticks) {
        int sum = 0;
        for (auto &num : matchsticks) sum += num;
        int edge = sum / 4;
        if (edge * 4 != sum) return false;
        sort(matchsticks.begin(), matchsticks.end(),
             [&](int a, int b) -> bool { return b < a; });
        vector<int> list(4, 0);
        return dfs(edge, list, 0, matchsticks);
    }
    bool dfs(int &edge, vector<int> &list, int idx, vector<int> &matchsticks) {
        if (idx == matchsticks.size()) {
            for (auto &num : list) {
                if (num != edge) return false;
            }
            return true;
        }
        for (int i = 0; i < 4; i++) {
            if (list[i] >= edge || list[i] + matchsticks[idx] > edge) continue;
            list[i] += matchsticks[idx];
            if (dfs(edge, list, idx + 1, matchsticks)) return true;
            list[i] -= matchsticks[idx];
        }
        return false;
    }
};

题解 2 - typescript

• 编辑时间：2021-07-25
• 执行用时：344ms
• 内存消耗：40.7MB
• 编程语言：typescript
• 解法介绍：dfs+剪枝，当前桶容量小于最小木棍时，舍弃。

function makesquare(matchsticks: number[]): boolean {
  matchsticks.sort((a, b) => b - a);
  const sum = matchsticks.reduce((total, cur) => total + cur, 0);
  const list: number[] = new Array(4).fill(sum / 4);
  return dfs();
  function dfs(index = 0): boolean {
    if (index === matchsticks.length) return list.every(v => v === 0);
    const num = matchsticks[index];
    for (let i = 0; i < 4; i++) {
      if (list[i] < num) continue;
      if (list[i] < matchsticks[matchsticks.length - 1]) return false;
      list[i] -= num;
      if (dfs(index + 1)) return true;
      list[i] += num;
    }
    return false;
  }
}