473.火柴拼正方形⭐

题目

火柴拼正方形

思路

为了减少搜索量，需要对火柴长度从大到小进行排序。

题解

• 题解1

class Solution {
public:
    bool dfs(int index, vector<int> &matchsticks, vector<int> &edges, int len) {
        if (index == matchsticks.size()) {
            return true;
        }
        for (int i = 0; i < edges.size(); i++) {
            edges[i] += matchsticks[index];
            if (edges[i] <= len && dfs(index + 1, matchsticks, edges, len)) {
                return true;
            }
            edges[i] -= matchsticks[index];
        }
        return false;
    }

    bool makesquare(vector<int> &matchsticks) {
        int totalLen = accumulate(matchsticks.begin(), matchsticks.end(), 0);
        if (totalLen % 4 != 0) {
            return false;
        }
        sort(matchsticks.begin(), matchsticks.end(), greater<int>()); // 减少搜索量

        vector<int> edges(4);
        return dfs(0, matchsticks, edges, totalLen / 4);
    }
};

• 时间复杂度：O(4 ^ n)，其中 n 是数组中元素的个数
• 空间复杂度：O(n)，递归栈需要占 O(n) 的空间

执行用时：248 ms, 在所有 C++ 提交中击败了20.09%的用户

内存消耗：9.6 MB, 在所有 C++ 提交中击败了76.84%的用户

通过测试用例：185 / 185