Question

473. 火柴拼正方形

English Version

题目描述

你将得到一个整数数组 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

解法

方法一：排序 + 回溯

用 $edges[i]$ 记录正方形每条边当前的长度，对于第 $u$ 根火柴，尝试把它加到 $edges[i]$ 每条边，若加入后 $edges[i]$ 不超过正方形期望长度 $x$，则继续往下递归 $u+1$ 根火柴。若所有火柴都能被加入，说明满足拼成正方形的要求。

这里对 $matchsticks$ 从大到小排序，可以减少搜索次数。

时间复杂度 $O(4^n)$，其中 $n$ 表示 $matchsticks$ 的长度。每根火柴可以被放入正方形的 $4$ 条边，共有 $n$ 根火柴。

class Solution:
  def makesquare(self, matchsticks: List[int]) -> bool:
    def dfs(u):
      if u == len(matchsticks):
        return True
      for i in range(4):
        if i > 0 and edges[i - 1] == edges[i]:
          continue
        edges[i] += matchsticks[u]
        if edges[i] <= x and dfs(u + 1):
          return True
        edges[i] -= matchsticks[u]
      return False

    x, mod = divmod(sum(matchsticks), 4)
    if mod or x < max(matchsticks):
      return False
    edges = [0] * 4
    matchsticks.sort(reverse=True)
    return dfs(0)

class Solution {
  public boolean makesquare(int[] matchsticks) {
    int s = 0, mx = 0;
    for (int v : matchsticks) {
      s += v;
      mx = Math.max(mx, v);
    }
    int x = s / 4, mod = s % 4;
    if (mod != 0 || x < mx) {
      return false;
    }
    Arrays.sort(matchsticks);
    int[] edges = new int[4];
    return dfs(matchsticks.length - 1, x, matchsticks, edges);
  }

  private boolean dfs(int u, int x, int[] matchsticks, int[] edges) {
    if (u < 0) {
      return true;
    }
    for (int i = 0; i < 4; ++i) {
      if (i > 0 && edges[i - 1] == edges[i]) {
        continue;
      }
      edges[i] += matchsticks[u];
      if (edges[i] <= x && dfs(u - 1, x, matchsticks, edges)) {
        return true;
      }
      edges[i] -= matchsticks[u];
    }
    return false;
  }
}

class Solution {
public:
  bool makesquare(vector<int>& matchsticks) {
    int s = 0, mx = 0;
    for (int& v : matchsticks) {
      s += v;
      mx = max(mx, v);
    }
    int x = s / 4, mod = s % 4;
    if (mod != 0 || x < mx) return false;
    sort(matchsticks.begin(), matchsticks.end(), greater<int>());
    vector<int> edges(4);
    return dfs(0, x, matchsticks, edges);
  }

  bool dfs(int u, int x, vector<int>& matchsticks, vector<int>& edges) {
    if (u == matchsticks.size()) return true;
    for (int i = 0; i < 4; ++i) {
      if (i > 0 && edges[i - 1] == edges[i]) continue;
      edges[i] += matchsticks[u];
      if (edges[i] <= x && dfs(u + 1, x, matchsticks, edges)) return true;
      edges[i] -= matchsticks[u];
    }
    return false;
  }
};

func makesquare(matchsticks []int) bool {
  s := 0
  for _, v := range matchsticks {
    s += v
  }
  if s%4 != 0 {
    return false
  }
  sort.Sort(sort.Reverse(sort.IntSlice(matchsticks)))
  edges := make([]int, 4)
  var dfs func(u, x int) bool
  dfs = func(u, x int) bool {
    if u == len(matchsticks) {
      return true
    }
    for i := 0; i < 4; i++ {
      if i > 0 && edges[i-1] == edges[i] {
        continue
      }
      edges[i] += matchsticks[u]
      if edges[i] <= x && dfs(u+1, x) {
        return true
      }
      edges[i] -= matchsticks[u]
    }
    return false
  }
  return dfs(0, s/4)
}

impl Solution {
  pub fn makesquare(matchsticks: Vec<i32>) -> bool {
    let mut matchsticks = matchsticks;

    fn dfs(matchsticks: &Vec<i32>, edges: &mut [i32; 4], u: usize, x: i32) -> bool {
      if u == matchsticks.len() {
        return true;
      }
      for i in 0..4 {
        if i > 0 && edges[i - 1] == edges[i] {
          continue;
        }
        edges[i] += matchsticks[u];
        if edges[i] <= x && dfs(matchsticks, edges, u + 1, x) {
          return true;
        }
        edges[i] -= matchsticks[u];
      }
      false
    }

    let sum: i32 = matchsticks.iter().sum();
    if sum % 4 != 0 {
      return false;
    }
    matchsticks.sort_by(|x, y| y.cmp(x));
    let mut edges = [0; 4];

    dfs(&matchsticks, &mut edges, 0, sum / 4)
  }
}

方法二：状态压缩 + 记忆化搜索

记当前火柴被划分的情况为 $state$。对于第 $i$ 个数，若 $state \ \& \ (1<<i)=0$，说明第 $i$ 个火柴棒未被划分。我们的目标是从全部数字中凑出 $k$ 个和为 $s$ 的子集。

记当前子集的和为 $t$。在未划分第 $i$ 个火柴棒时：

• 若 $t+matchsticks[i]>s$，说明第 $i$ 个火柴棒不能被添加到当前子集中，由于我们对 $matchsticks$ 数组进行升序排列，因此从 $matchsticks$ 从第 $i$ 个火柴棒开始的所有数字都不能被添加到当前子集，直接返回 $false$。
• 否则，将第 $i$ 个火柴棒添加到当前子集中，状态变为 $state \ |\ (1<<i)$，继续对未划分的数字进行搜索。

注：若 $t+matchsticks[i]==s$，说明恰好可以得到一个和为 $s$ 的子集，下一步将 $t$ 归零（可以通过 $(t+matchsticks[i]) \%s$ 实现），并继续划分下一个子集。

class Solution:
  def makesquare(self, matchsticks: List[int]) -> bool:
    @cache
    def dfs(state, t):
      if state == (1 << len(matchsticks)) - 1:
        return True
      for i, v in enumerate(matchsticks):
        if state & (1 << i):
          continue
        if t + v > s:
          break
        if dfs(state | (1 << i), (t + v) % s):
          return True
      return False

    s, mod = divmod(sum(matchsticks), 4)
    matchsticks.sort()
    if mod:
      return False
    return dfs(0, 0)