Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 473. Matchsticks to Square

---

題目：


解答：

class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        int n = matchsticks.size();
        int sum = accumulate(matchsticks.begin(), matchsticks.end(), 0);

        if (sum % 4) {
            return false;
        }

        int target = sum / 4;
        vector<int> side(4, 0);

        sort(matchsticks.begin(), matchsticks.end());

        if (matchsticks[0] > target) {
            return false;
        }

        auto dfs = [&](this auto&& dfs, int idx) {
            if (idx == n) {
                return side[0] == target &&
                    side[1] == target &&
                    side[2] == target &&
                    side[3] == target;
            }

            int add = matchsticks[idx];

            for (int i = 0; i < 4; ++i) {
                if (side[i] + add > target) {
                    continue;
                }

                side[i] += add;
                if (dfs(idx + 1)) {
                    return true;
                }
                side[i] -= add;

                if (side[i] == 0) {
                    break;
                }
            }

            return false;
        };

        return dfs(0);
    }
};