leetcode

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 };