# 473. Matchsticks to Square

• Time: $O(2^n)$
• Space: $O(2^n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 class Solution { public: bool makesquare(vector& matchsticks) { if (matchsticks.size() < 4) return false; const int perimeter = accumulate(begin(matchsticks), end(matchsticks), 0); if (perimeter % 4 != 0) return false; sort(begin(matchsticks), end(matchsticks), greater()); return dfs(matchsticks, 0, vector(4, perimeter / 4)); } private: bool dfs(const vector& matchsticks, int selected, vector&& edges) { if (selected == matchsticks.size()) return all_of(begin(edges), end(edges), [](int edge) { return edge == 0; }); for (int i = 0; i < 4; ++i) { if (matchsticks[selected] > edges[i]) continue; edges[i] -= matchsticks[selected]; if (dfs(matchsticks, selected + 1, move(edges))) return true; edges[i] += matchsticks[selected]; } return false; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 class Solution { public boolean makesquare(int[] matchsticks) { if (matchsticks.length < 4) return false; final int perimeter = Arrays.stream(matchsticks).sum(); if (perimeter % 4 != 0) return false; int[] edges = new int[4]; Arrays.fill(edges, perimeter / 4); Arrays.sort(edges); // can't do "Arrays.sort(edges, (a, b) -> b - a);" in Java return dfs(matchsticks, matchsticks.length - 1, edges); } private boolean dfs(int[] matchsticks, int selected, int[] edges) { if (selected == -1) return Arrays.stream(edges).allMatch(edge -> edge == 0); for (int i = 0; i < 4; ++i) { if (matchsticks[selected] > edges[i]) continue; edges[i] -= matchsticks[selected]; if (dfs(matchsticks, selected - 1, edges)) return true; edges[i] += matchsticks[selected]; } return false; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution: def makesquare(self, matchsticks: List[int]) -> bool: if len(matchsticks) < 4: return False perimeter = sum(matchsticks) if perimeter % 4 != 0: return False A = sorted(matchsticks)[::-1] def dfs(selected: int, edges: List[int]) -> bool: if selected == len(A): return all(edge == edges[0] for edge in edges) for i, edge in enumerate(edges): if A[selected] > edge: continue edges[i] -= A[selected] if dfs(selected + 1, edges): return True edges[i] += A[selected] return False return dfs(0, [perimeter // 4] * 4)