用火柴拼出一个正方形

20 Oct 2024 in Algorithm Pageviews

回溯

你将得到一个整数数组 matchsticks ，其中 matchsticks[i] 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。你 不能折断 任何一根火柴棒，但你可以把它们连在一起，而且每根火柴棒必须 使用一次 。

如果你能拼成个正方形，则返回 true ，否则返回 false 。

示例1

输入

matchsticks = [1,1,2,2,2]

输出

true

代码输出如下

#include <bits/stdc++.h>

using namespace std;

class Solution {
public:
    bool dfs(vector<int> &nums, int u, int cur, int length)
    {
        if (cur == length) {
            u++;
            cur = 0;
        }
        if (u == 4) {
            return true;
        }

        for (auto i = 0; i < nums.size(); i++) {
            if (st[i] || (cur + nums[i] > length)) {
                continue;
            }

            st[i] = true;
            if (dfs(nums, u, cur + nums[i], length)) {
                return true;
            }
            st[i] = false;
            if ((cur == 0) || (cur + nums[i] == length)) {
                return false;
            }
            
            while ((i + 1 < nums.size()) && (nums[i + 1] == nums[i])) {
                i++;
            }
        }
        return false;
    }

    bool MakeSquare(vector<int>& matchsticks)
    {
        auto sum = std::accumulate(matchsticks.begin(), matchsticks.end(), 0);
        if (sum == 0 || (sum % 4 != 0)) {
            return false;
        }
        
        sort(matchsticks.begin(), matchsticks.end(), std::less<int>());
        st = vector<bool>(matchsticks.size());
        return dfs(matchsticks, 0, 0, sum / 4);
    }

private:
    vector<bool> st;
};