vivek_ragi

MATCHSTICKS_TO_SQUARE

Jun 16th, 2021 (edited)
159
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     bool myfunc(vector<int> &M, int sum, vector<int> &vis, vector<int> &S, int idx) {
  4.        
  5.         if(idx == M.size()) {
  6.             if(S[0] == sum and S[1] == sum and S[2] == sum and S[3] == sum) {
  7.                 return true;
  8.             }
  9.         }
  10.        
  11.        
  12.         for(int i = 0; i < 4; ++i) {
  13.             if(vis[idx] or S[i] + M[idx] > sum) {
  14.                 continue;
  15.             }
  16.             vis[idx] = true;
  17.             //include
  18.             S[i] += M[idx];
  19.             if(myfunc(M, sum, vis, S, idx + 1)) {
  20.                 return true;
  21.             }
  22.             //exclude
  23.             S[i] -= M[idx];
  24.             vis[idx] = false;
  25.                
  26.         }
  27.         return false;
  28.     }
  29.    
  30.    
  31.     bool makesquare(vector<int>& M) {
  32.         int sum = 0;
  33.        
  34.         sum = accumulate(M.begin(), M.end(), sum);
  35.         sort(M.rbegin(), M.rend());
  36.        
  37.         if(M.size() < 4 or sum%4) {
  38.             return false;
  39.         }
  40.         sum/=4;
  41.         vector<int> vis(M.size(),0); //visited
  42.         vector<int> S(4,0); //sides
  43.        
  44.        
  45.         return myfunc(M, sum, vis, S, 0);
  46.     }
  47. };
RAW Paste Data