Problem Explanation

In this problem, you're given an array of integers where each integer represents the length of a matchstick the Little Match Girl possesses. The task is to determine whether these matchsticks can be arranged into a perfect square without any matchstick being left out or broken.

The condition for being able to form a square is that the sum of the lengths of the four sides must be the same. Thus, the total length of all the matchsticks must be divisible by 4. If it isn't, we can immediately return false.

If it is divisible by 4, then we need to check if there’s a combination of matchsticks that adds up to the same value (i.e., total length of matchsticks / 4). We're essentially trying to partition the matchsticks into four equal subsets.

Approach

• The problem is solved using a depth-first search (DFS) approach.
• Initially check if it's possible to partition the matchsticks by verifying if the sum is divisible by 4.
• If it is, then sort the list in decreasing order. This optimizes our search, since if a matchstick can’t be fit into a subset, then we don’t need to check the smaller ones.
• Next, we recursively try to add each matchstick to one of the four sides of the potential square (represented as a list 'edges'). If a matchstick fits (i.e., its length is less than or equal to the current edge length), we subtract its length from the current edge and call the recursive function with the next matchstick.
• If it doesn’t fit, we try with the next edge. If it fits into an edge, we check for the next matchstick. If no edges can accommodate the matchstick, we backtrack by undoing the changes made and return false.
• If all matchsticks are used (i.e., every edge length becomes 0), we return true.
• The function ultimately returns whether we can form a square or not.

Example

Let's walk-through a scenario where we have 5 matchsticks with lengths [1,1,2,2,2].

1. Check if sum of all matchsticks is divisible by 4: Sum = 8 which is divisible by 4. The target length for each edge of the square is Sum/4 = 2.

2. Sort matchsticks in reverse order: [2,2,2,1,1]

3. Trying to fit each matchstick into the four edges of the potential square.

We will have a square formed with [2,2,2,2] as its sides.

Solution in Python

1
2python
3class Solution:
4    def makesquare(self, nums):
5        if not nums:
6            return False
7
8        L, rem = divmod(sum(nums), 4)
9        if rem or max(nums) > L: 
10            return False
11        
12        nums.sort(reverse=True)
13        return self.dfs(nums, [0]*4, 0, L)
14            
15    def dfs(self, nums, sums, index, L):
16        if index == len(nums):
17            return sums[0] == L and sums[1] == L and sums[2] == L
18                
19        for i in range(4):
20            if sums[i] + nums[index] > L: 
21                continue
22            sums[i] += nums[index]
23            if self.dfs(nums, sums, index + 1, L): 
24                return True
25            sums[i] -= nums[index]
26            
27        return False

Solution in Java

1
2java
3class Solution {
4    public boolean makesquare(int[] matchsticks) {
5        if (matchsticks == null || matchsticks.length < 4)
6            return false;
7        int sum = 0;
8        for (int matchstick : matchsticks) {
9            sum += matchstick;
10        }
11        if (sum % 4 != 0) 
12            return false;
13        Arrays.sort(matchsticks);
14        return dfs(matchsticks, new int[4], matchsticks.length - 1, sum / 4);
15    }
16
17    private boolean dfs(int[] matchsticks, int[] sums, int i, int target) {
18        if (i < 0) 
19            return sums[0] == target && sums[1] == target && sums[2] == target;
20        for (int j = 0; j < 4; j++) {
21            if (sums[j] + matchsticks[i] > target) 
22                continue;
23            sums[j] += matchsticks[i];
24            if (dfs(matchsticks, sums, i - 1, target))
25                return true;
26            sums[j] -= matchsticks[i];
27        }
28        return false;
29    }
30}

Solution in Javascript

1
2javascript
3var makesquare = function(nums) {
4    if (nums.length < 4) return false;
5    const sum = nums.reduce((pre, cur) => pre + cur, 0);
6    if (sum % 4 !== 0) return false;
7    let edges = new Array(4).fill(sum / 4);
8    nums.sort((a, b) => b - a);
9    let dfs = function (index) {
10        if (index === nums.length) return true;
11        for (let i = 0; i < 4; i++) {
12            if (edges[i] >= nums[index]) {
13                edges[i] -= nums[index];
14                if (dfs(index + 1)) return true;
15                edges[i] += nums[index];
16            }
17        }
18        return false;
19    }
20    return dfs(0);
21};

The C# and C++ solutions are similar to the Python, Java, or Javascript solution, using a depth first search and the same logic. Nonetheless, the language syntax might differ.

Please do remember to check the function names and class/method declarations closely when implementing in a different language. Be aware of language-specific nuances, such as how to declare and initialize variables, how to use control structures (like for loops and if statements), and how to declare and instantiate classes.# Solution in C#

1
2csharp
3public class Solution {
4    public bool Makesquare(int[] nums) {
5        if (nums == null || nums.Length < 4) {
6            return false;
7        }
8        
9        int sum = 0;
10        foreach (int num in nums) {
11            sum += num;
12        }
13        
14        if (sum % 4 != 0) {
15            return false;
16        }
17        
18        Array.Sort(nums);
19        Array.Reverse(nums);
20        
21        return DFS(nums, new int[4], 0, sum / 4);
22    }
23    
24    private bool DFS(int[] nums, int[] sums, int index, int target) {
25        if (index == nums.Length) {
26            return sums[0] == target && sums[1] == target && sums[2] == target;
27        }
28        
29        for (int i = 0; i < 4; i++) {
30            if (sums[i] + nums[index] > target) {
31                continue;
32            }
33            
34            sums[i] += nums[index];
35            if (DFS(nums, sums, index + 1, target)) {
36                return true;
37            }
38            
39            sums[i] -= nums[index];
40        }
41        
42        return false;
43    }
44}

Solution in C++

1
2cpp
3class Solution {
4public:
5    bool makesquare(vector<int>& nums) {
6        if (nums.size() < 4) {
7            return false;
8        }
9        
10        int sum = accumulate(nums.begin(), nums.end(), 0);
11        if (sum % 4 != 0) {
12            return false;
13        }
14        
15        sort(nums.begin(), nums.end(), greater<int>());
16        
17        vector<int> sums(4, 0);
18        return dfs(nums, sums, 0, sum / 4);
19    }
20    
21    bool dfs(vector<int>& nums, vector<int>& sums, int index, int target) {
22        if (index == nums.size()) {
23            return sums[0] == target && sums[1] == target && sums[2] == target;
24        }
25        
26        for (int i = 0; i < 4; i++) {
27            if (sums[i] + nums[index] > target) {
28                continue;
29            }
30            
31            sums[i] += nums[index];
32            if (dfs(nums, sums, index + 1, target)) {
33                return true;
34            }
35            
36            sums[i] -= nums[index];
37        }
38        
39        return false;
40    }
41};

Both the C# and C++ solutions follow the same approach as the previous ones. They first check if the total length of the matchsticks is divisible by 4, and if it is, they use recursion to verify if the matchstick lengths can be partitioned into 4 groups that each add up to the target length.

While implementing the solutions, keep in mind that the syntax, particularly for array operations and function declarations, can vary between languages. Remember to give attention to these differences to avoid compilation errors.