• Time:O(2^n)
• Space:O(2^n)

## C++

``````class Solution {
public:
bool makesquare(vector<int>& 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<int>());
return dfs(matchsticks, 0, vector<int>(4, perimeter / 4));
}

private:
bool dfs(const vector<int>& matchsticks, int selected, vector<int>&& 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;
}
};
``````

## JAVA

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

## Python

``````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)
``````