Leetcode 473. Match to square [violence + pruning]

subject

Main idea and ideas

The meaning of the title is to give an array , It is required to judge whether the numbers in the array can be divided into 4 Share . First initialize the four edges with the length of 0, Try adding a match to one of the edges in turn . The method of pruning is written in the notes .

Code

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;  //  One edge is greater than the total number of 1/4,  Return early false
            if(l1+left < sum || l2+left < sum || l3+left<sum || l4+left<sum) return false;  //  One side plus all the remaining matches is still less than the total 1/4,  Return early false
            if(cur == vec.size()) {
      //  Reach the root of the permutation tree 
                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:
        //  Judge whether it can be quartered 
        bool makesquare(vector<int>& matchsticks) {
    
            sum = 0;
            for(auto i : matchsticks) sum += i;
            sum /= 4;
            sort(matchsticks.begin(), matchsticks.end(), this->cmp);  //  First assign a large match ,  Good for pruning 
            return check(0, 0, 0, 0, 0, matchsticks, sum*4);
        }
};

result