473.matchsticks-to-square.md

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

输入: [1,1,2,2,2]
输出: true

解释: 能拼成一个边长为2的正方形，每边两根火柴。
示例 2:

输入: [3,3,3,3,4]
输出: false

解释: 不能用所有火柴拼成一个正方形。

注意:

• 给定的火柴长度和在  0  到  10^9 之间。
• 火柴数组的长度不超过 15。

---

思路

dfs + 回溯 + 剪枝

剪枝优化的经典题目

代码实现

cpp

class Solution {
    vector<bool> st;
public:
    bool makesquare(vector<int> &nums) {
        int sum = 0;
        for (auto u : nums) sum += u;
        if (!sum || sum % 4 != 0) return false; // 总长度不能被4整除

        sort(nums.begin(), nums.end(), greater<int>()); // 从长到短排序

        st = vector<bool>(nums.size());
        return dfs(nums, 0, 0, sum / 4); // 第几条边，当前边的长度，当前边的总长度
    }

    bool dfs(vector<int> nums, int u, int cur, int length) {
        if (cur == length) u++, cur = 0;
        if (u == 4) return true;

        for (int i = 0; i < nums.size(); i++) {
            if (!st[i] && cur + nums[i] <= length) {
                st[i] = true; // 用第i根火柴
                if (dfs(nums, u, cur + nums[i], length)) return true;
                st[i] = false;
                if (!cur) return false;
                if (cur + nums[i] == length) return false;
                while (i + 1 < nums.size() && nums[i + 1] == nums[i]) i++;
            }
        }
        return false;
    }
};