Table of Contents

# Matchsticks to Square – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

You are given an integer array `matchsticks`

where `matchsticks[i]`

is the length of the `i`

matchstick. You want to use ^{th}**all the matchsticks** to make one square. You **should not break** any stick, but you can link them up, and each matchstick must be used **exactly one time**.

Return `true`

if you can make this square and `false`

otherwise.

**Example 1:**

Input:matchsticks = [1,1,2,2,2]Output:trueExplanation:You can form a square with length 2, one side of the square came two sticks with length 1.

**Example 2:**

Input:matchsticks = [3,3,3,3,4]Output:falseExplanation:You cannot find a way to form a square with all the matchsticks.

**Constraints:**

`1 <= matchsticks.length <= 15`

`1 <= matchsticks[i] <= 10`

^{8}

# C++ Matchsticks to Square LeetCode Solution

```
``````
class Solution {
bool dfs(vector<int> &sidesLength,const vector<int> &matches, int index) {
if (index == matches.size())
return sidesLength[0] == sidesLength[1] && sidesLength[1] == sidesLength[2] && sidesLength[2] == sidesLength[3];
for (int i = 0; i < 4; ++i) {
sidesLength[i] += matches[index];
if (dfs(sidesLength, matches, index + 1))
return true;
sidesLength[i] -= matches[index];
}
return false;
}
public:
bool makesquare(vector<int>& nums) {
if (nums.empty()) return false;
vector<int> sidesLength(4, 0);
return dfs(sidesLength, nums, 0);
}
};
```

# Java Matchsticks to Square LeetCode Solution

```
``````
public class Solution {
public boolean makesquare(int[] nums) {
if (nums == null || nums.length < 4) return false;
int sum = 0;
for (int num : nums) sum += num;
if (sum % 4 != 0) return false;
return dfs(nums, new int[4], 0, sum / 4);
}
private boolean dfs(int[] nums, int[] sums, int index, int target) {
if (index == nums.length) {
if (sums[0] == target && sums[1] == target && sums[2] == target) {
return true;
}
return false;
}
for (int i = 0; i < 4; i++) {
if (sums[i] + nums[index] > target) continue;
sums[i] += nums[index];
if (dfs(nums, sums, index + 1, target)) return true;
sums[i] -= nums[index];
}
return false;
}
}
```

# Python 3 Matchsticks to Square LeetCode Solution

```
``````
class Solution:
def makesquare(self, nums):
N = len(nums)
basket, rem = divmod(sum(nums), 4)
if rem or max(nums) > basket: return False
@lru_cache(None)
def dfs(mask):
if mask == 0: return 0
for j in range(N):
if mask & 1<<j:
neib = dfs(mask ^ 1<<j)
if neib >= 0 and neib + nums[j] <= basket:
return (neib + nums[j]) % basket
return -1
return dfs((1<<N) - 1) == 0
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1