Leetcode 473. 火柴拼正方形 [暴力+剪枝]

题目

题目大意及思路

题目的意思就是给定一个数组，要求判断能否将数组中的数字平均分为4份。先初始化四个边长度为0，依次尝试将一个火柴添加到其中一条边上。剪枝的方法写在注释里。

代码

class Solution {
    
    int sum;
        bool check(int l1, int l2, int l3, int l4, int cur, vector<int>& vec, int left) {
    
            if(l1 > sum || l2 > sum || l3 > sum || l4 > sum) return false;  // 某一条边大于总数的1/4, 提前返回false
            if(l1+left < sum || l2+left < sum || l3+left<sum || l4+left<sum) return false;  // 某一条边加上剩下的所有火柴仍达不到总数的1/4, 提前返回false
            if(cur == vec.size()) {
      // 达到排列树的根
                if( l1 == l2 && l2 == l3 && l3 == l4) {
     return true; }
                else return false;
            }
            int l = left-vec[cur];
            return (
                    check(l1+vec[cur], l2, l3, l4, cur+1, vec, l) ||
                    check(l1, l2+vec[cur], l3, l4, cur+1, vec, l) ||
                    check(l1, l2, l3, l4+vec[cur], cur+1, vec, l) ||
                    check(l1, l2, l3+vec[cur], l4, cur+1, vec, l)
                    );
        }
        static bool cmp(const int& a, const int& b) {
    
            return a > b;
        }
    public:
        // 判断能否四等分
        bool makesquare(vector<int>& matchsticks) {
    
            sum = 0;
            for(auto i : matchsticks) sum += i;
            sum /= 4;
            sort(matchsticks.begin(), matchsticks.end(), this->cmp);  // 先分配大的火柴, 有利于剪枝
            return check(0, 0, 0, 0, 0, matchsticks, sum*4);
        }
};

结果