leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0473.cpp (1648B)

0 // Backtracking: 4 ^ N 1 class Solution { 2 static bool find(const vector<int> &sticks, const int side, int idx, int crnt[4]) { 3 if (idx == size(sticks)) return crnt[0] == side && crnt[1] == side && crnt[2] == side; 4 5 for (int i = 0; i < 4; i++) { 6 if (crnt[i] + sticks[idx] > side) continue; 7 8 crnt[i] += sticks[idx]; 9 if (find(sticks, side, idx + 1, crnt)) return true; 10 crnt[i] -= sticks[idx]; 11 } 12 13 return false; 14 } 15 16 public: 17 bool makesquare(vector<int> &sticks) const { 18 const int sum = accumulate(begin(sticks), end(sticks), 0); 19 if (sum % 4 != 0) return false; 20 21 sort(begin(sticks), end(sticks), greater<>()); 22 int crnt[4] = {sticks[0], 0}; 23 return find(sticks, sum / 4, 1, crnt); 24 } 25 }; 26 27 // DP: N * 2 ^ N 28 class Solution { 29 uint8_t dp[4][1 << 16] = {0}; 30 31 bool find(const vector<int> &sticks, int left, int side, int crnt, uint16_t mask) { 32 if (dp[left][mask]) return false; 33 dp[left][mask] = 1; 34 35 if (crnt == side) left--, crnt = 0; 36 if (!left) return true; 37 38 for (int i = 0, msk = 1; i < size(sticks); i++, msk <<= 1) { 39 if (mask & msk) continue; 40 if (crnt + sticks[i] > side) continue; 41 if (find(sticks, left, side, crnt + sticks[i], mask | msk)) return true; 42 } 43 44 return false; 45 } 46 47 public: 48 bool makesquare(vector<int> &sticks) { 49 const int sum = accumulate(begin(sticks), end(sticks), 0); 50 if (sum % 4 != 0) return false; 51 52 const int side = sum / 4; 53 return find(sticks, 3, side, 0, 0); 54 } 55 };