You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick. You want to use 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: true
Explanation: 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: false
Explanation: You cannot find a way to form a square with all the matchsticks.
Constraints:
1 <= matchsticks.length <= 150 <= matchsticks[i] <= 109Matchsticks to Square - LeetCode
First Optimization:
Each matchstick must be used exactly one time.
The description says we need to use every single match exactly once, so we can get the length of each side of the square if there is one.if the current length is larger than target length, we don't need to go any further.if (sidesLength[i] + matches[index] > target) continue; by adding this line of code into dfs function, solution get TLE at 147th test case.
Second Optimization: