【DFS, 回溯】火柴拼正方形

题目

473. 火柴拼正方形

---

你将得到一个整数数组 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] <= 10^8

解题

方法一：DFS 回溯 排序 剪枝

思路

先求出所有火柴的长度总和(sum)，如果 sum 不是 $4$ 的倍数那么一定不能拼成正方形，直接返回 false，否则记录每条边的长度($edgeLen = \frac{sum}{4}$)。

然后就可以爆搜+回溯：对于每一根(idx)火柴，尝试放入每一条边(edges[i])，如果放入之后边的长度大于 edgeLen 就需要进行剪枝，否则继续枚举下一个火柴，如果之后的某根火柴无法被正确放置就需要回溯，退回到前一根火柴尝试下一条边，否则所有火柴都被放好就说明可以拼成正方形。

参考：https://leetcode.cn/problems/matchsticks-to-square/solution/hui-su-suan-fa-jie-jue-ji-you-hua-chao-g-9iyl/

代码

DFS + 回溯 + 剪枝(超时)

class Solution {
    int n, edgeLen;
    int[] msArr, edges = new int[4];

    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for (int len : matchsticks) sum += len;
        if (sum % 4 != 0) return false;
        edgeLen = sum / 4; 
        msArr = matchsticks;
        n = msArr.length;
        return dfs(0);
    }

    public boolean dfs(int idx) {
        if (idx == n && edges[0] == edgeLen && edges[1] == edgeLen &&
            edges[2] == edgeLen && edges[3] == edgeLen) return true;
        int curr = msArr[idx];
        for (int i = 0; i < 4; ++i) {
            if (edges[i] + curr > edgeLen) continue; 
            edges[i] += curr;
            if (edges[i] <= edgeLen && dfs(idx + 1)) return true;
            edges[i] -= curr;
        }
        return false;
    }
}

把火柴(matchsticks)降序排序可以有效的减少搜索量，因为如果火柴数组中前面有很多短火柴的话每次尝试都很难超过 edgeLen 造成多了很多错误的尝试，把较长的火柴放在前面可以提高剪枝率(通过)。

class Solution { 
    int edge_len, n;
    vector<int> ms_lens;
    vector<int> edges;

public:
    bool makesquare(vector<int>& matchsticks) {
        int sum = accumulate(matchsticks.begin(), matchsticks.end(), 0);
        if (sum % 4 != 0) return false;
        edge_len = sum / 4;
        n = matchsticks.size();
        ms_lens = matchsticks;
        sort(ms_lens.begin(), ms_lens.end(), greater<int>());
        edges.resize(4);
        return dfs(0);
    }

    bool dfs(int idx) {
        if (idx == n) return true;
        int& curr = ms_lens[idx];
        for (int i = 0; i < 4; ++i) {
            if (edges[i] + curr > edge_len) continue;
            edges[i] += curr;
            if (dfs(idx + 1)) return true;
            edges[i] -= curr;
        }
        return false;
    }
};

(Java int 数组不能方便的降序排序，于是升序排序反着搜索)。

class Solution {
    int edgeLen;
    int[] msArr, edges = new int[4];

    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for (int len : matchsticks) sum += len;
        if (sum % 4 != 0) return false;
        edgeLen = sum / 4;
        msArr = matchsticks;
        Arrays.sort(msArr);
        return dfs(msArr.length - 1);
    }

    public boolean dfs(int idx) {
        if (idx == -1) return true;
        int curr = msArr[idx];
        for (int i = 0; i < 4; ++i) {
            if (edges[i] + curr > edgeLen) continue; 
            edges[i] += curr;
            if (dfs(idx - 1)) return true;
            edges[i] -= curr;
        }
        return false;
    }
}

剪枝：

if (i > 0 && edges[i] == edges[i - 1]) continue;

表示如果当前边与上一个边的长度相同，则跳过。
原因：如果边长相等，那么把当前火柴加入 edges[i] 加入 edges[i - 1] 递归的结果是一致的。

这个剪枝直接把运行时间从上百毫秒减少到了个位数：

参考：https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/solution/by-lfool-d9o7/ 中的第二次尝试剪枝

class Solution {
    int edgeLen;
    int[] msArr, edges = new int[4];

    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        for (int len : matchsticks) sum += len;
        if (sum % 4 != 0) return false;
        edgeLen = sum / 4;
        msArr = matchsticks;
        Arrays.sort(msArr);
        return dfs(msArr.length - 1);
    }

    public boolean dfs(int idx) {
        if (idx == -1) return true;
        int curr = msArr[idx];
        for (int i = 0; i < 4; ++i) {
            if (edges[i] + curr > edgeLen ||
                i > 0 && edges[i] == edges[i - 1]) continue; 
            edges[i] += curr;
            if (edges[i] <= edgeLen && dfs(idx - 1)) return true;
            edges[i] -= curr;
        }
        return false;
    }
}

class Solution { 
    int edge_len, n;
    vector<int> ms_lens;
    vector<int> edges;

public:
    bool makesquare(vector<int>& matchsticks) {
        int sum = accumulate(matchsticks.begin(), matchsticks.end(), 0);
        if (sum % 4 != 0) return false;
        edge_len = sum / 4;
        n = matchsticks.size();
        ms_lens = matchsticks;
        sort(ms_lens.begin(), ms_lens.end(), greater<int>());
        edges.resize(4);
        return dfs(0);
    }

    bool dfs(int idx) {
        if (idx == n) return true;
        int& curr = ms_lens[idx];
        for (int i = 0; i < 4; ++i) {
            if (edges[i] + curr > edge_len ||
                i > 0 && edges[i] == edges[i - 1]) continue;
            edges[i] += curr;
            if (dfs(idx + 1)) return true;
            edges[i] -= curr;
        }
        return false;
    }
};