【Leetcode】473. Matchsticks to Square

题目地址：

https://leetcode.com/problems/matchsticks-to-square/

给定一个长$n$正整数数组$A$，代表若干个小木棍的长度，要求将这些小木棍拼成一个大正方形，使得所有的小木棍都恰好用完。问是否可能。

参考https://blog.csdn.net/qq_46105170/article/details/115562806。我们可以从长到短枚举当前应该放哪个小木棍，剪枝可以参考链接。代码如下：

class Solution {
    
 public:
  int len;
  bool makesquare(vector<int> &A) {
    
    len = 0;
    for (auto &x : A) len += x;
    // 不是4的倍数，说明无解
    if (len % 4) return false;
    len /= 4;

    sort(A.begin(), A.end(), greater<int>());
    vector<bool> vis(A.size(), 0);
    return dfs(0, 0, 0, A, vis);
  }

  bool dfs(int u, int cur_len, int cnt, vector<int> &A, vector<bool> &vis) {
    
    if (cnt == 3) return true;
    if (cur_len == len) return dfs(0, 0, cnt + 1, A, vis);

    for (int i = u; i < A.size(); i++) {
    
      if (vis[i]) continue;
      if (cur_len + A[i] > len) continue;
      cur_len += A[i];
      vis[i] = true;
      if (dfs(u + 1, cur_len, cnt, A, vis)) return true;
      cur_len -= A[i];
      vis[i] = false;
      if (!cur_len || cur_len + A[i] == len) return false;
      while (i + 1 < A.size() && A[i + 1] == A[i]) i++;
    }

    return false;
  }
};

时间复杂度指数级，空间$O(n)$。

Java：

import java.util.Arrays;

public class Solution {
    
    public boolean makesquare(int[] A) {
    
        int len = 0;
        for (int x : A) {
    
            len += x;
        }
        if (len % 4 != 0) {
    
            return false;
        }
        
        len /= 4;
        Arrays.sort(A);
        reverse(A);
        boolean[] vis = new boolean[A.length];
        return dfs(0, 0, len, 0, A, vis);
    }
    
    void reverse(int[] A) {
    
        for (int i = 0, j = A.length - 1; i < j; i++, j--) {
    
            int tmp = A[i];
            A[i] = A[j];
            A[j] = tmp;
        }
    }
    
    boolean dfs(int u, int curLen, int len, int cnt, int[] A, boolean[] vis) {
    
        if (cnt == 3) {
    
            return true;
        }
        if (curLen == len) {
    
            return dfs(0, 0, len, cnt + 1, A, vis);
        }
        
        for (int i = u; i < A.length; i++) {
    
            if (vis[i] || curLen + A[i] > len) {
    
                continue;
            }
            
            vis[i] = true;
            curLen += A[i];
            if (dfs(u + 1, curLen, len, cnt, A, vis)) {
    
                return true;
            }
            vis[i] = false;
            curLen -= A[i];
            if (curLen == 0 || curLen + A[i] == len) {
    
                return false;
            }
            while (i + 1 < A.length && A[i + 1] == A[i]) {
    
                i++;
            }
        }
        
        return false;
    }
}

时空复杂度一样。