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.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= matchsticks.length &lt;= 15
	1 &lt;= matchsticks[i] &lt;= 108


class Solution:
    def makesquare(self, matchsticks: List[int]) -> bool:
        target,m=divmod(sum(matchsticks),4)
        if m:return False
        targetLst=[0]*4
        length=len(matchsticks)
        matchsticks.sort(reverse=True)
        def bt(i):
            if i==length:
                return len(set(targetLst))==1
            for j in range(4):
                if matchsticks[i]+targetLst[j]>target:
                    continue
                targetLst[j]+=matchsticks[i]
                if bt(i+1):
                    return True
                targetLst[j]-=matchsticks[i]
                if not targetLst[j]:break
            return False
        return matchsticks[0]<=target and bt(0)
/*
    Time complexity: O(2 ^ n)
    Space complexity: O(n)

    Inutition:
    ---------
    Same as "Partition to K Equal Sum Subsets"
*/

class Solution {
    public boolean backtrack(int[] nums, int idx, int k, int subsetSum, int target, boolean[] vis) {
        // base case
        if (k == 0)
            return true;
        if (target == subsetSum) {
            // if one of the side is found then keep finding the other k - 1 sides starting again from the beginning
            return backtrack(nums, 0, k - 1, 0, target, vis);
        }

        // hypothesis
        for(int i = idx; i < nums.length; i++) {
            // if number is already visited or sum if out of range then skip
            if (vis[i] || subsetSum + nums[i] > target)
                continue;

            // Pruning
            // if the last position (i - 1) is not visited, that means the current combination didn't work,
            // and since this position (i) has the same value, it won't work for it as well. Thus, skip it.
            if (i - 1 >= 0 && nums[i] == nums[i - 1] && !vis[i - 1])
                continue;

            vis[i] = true;
            if (backtrack(nums, i + 1, k, subsetSum + nums[i], target, vis))
                return true;

            // backtrack
            vis[i] = false;
        }

        return false;
    }

    private void reverse(int[] arr) {
        for (int i = 0, j = arr.length - 1; i < j; i++, j--) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }

    public boolean makesquare(int[] matchsticks) {
        int sum = 0;
        int k = 4;
        int n = matchsticks.length;
        // sort the array in descending order to make the recursion hit the base case quicker
        Arrays.sort(matchsticks);
        reverse(matchsticks);

        for(int match: matchsticks)
            sum += match;

        if (sum % k != 0)
            return false;

        int target = sum / k;
        boolean[] vis = new boolean[n];

        return backtrack(matchsticks, 0, k, 0, target, vis);
    }
}
class Solution {
public:
    bool makesquare(vector<int>& matchsticks) {
        int goal = 0, totalSum = 0;
        for (int i : matchsticks) {
            totalSum += i;
        }
        goal = totalSum / 4;
        sort(matchsticks.begin(), matchsticks.end(), [](auto left, auto right) {
            return left > right;
        });
        int b = 0;
        if (totalSum % 4) {
            return false;
        }
        return backtrack(0, b, 0, goal, 4, matchsticks);
    }
    
    bool backtrack(int start, int &b, int sum, int &goal, int groups, vector<int>& matchsticks) {
        if (sum == goal) {
            //set sum to 0, groups--
            return backtrack(0, b, 0, goal, groups-1, matchsticks);
        }
        if (groups == 1) {
            return true;
        }
        for (int i = start; i < matchsticks.size(); i++) {
            if ((i > 0) && (!(b & (1 << (i - 1)))) && (matchsticks[i] == matchsticks[i-1])) {
                continue;
            }
            //if element not used and element value doesnt go over group sum
            if (((b & (1 << i)) == 0) && (sum + matchsticks[i] <= goal)) {
                //set element to used, recursion
                b ^= (1 << i); 
                if (backtrack(i + 1, b, sum + matchsticks[i], goal, groups, matchsticks)) {
                    return true;
                }
                //if here, received a false, set element to unused again
                b ^= (1 << i);
            }
        }
        return false;
    }
};
var makesquare = function(matchsticks) {
    const perimeter = matchsticks.reduce((a, b) => a + b, 0);
    if(perimeter % 4 != 0 || matchsticks.length < 4) return false;
    
    const sideLen = perimeter / 4;
    // find a way to divide the array in 4 group of sum side length
    const sides = new Array(4).fill(0);
    const len = matchsticks.length;
    matchsticks.sort((a, b) => b - a);
    
    const solve = (x = 0) => {
        if(x == len) {
            return sides.every(side => side == sideLen);
        }
        
        for(let i = 0; i < 4; i++) {
            if(sides[i] + matchsticks[x] > sideLen) {
                continue;
            }
            sides[i] += matchsticks[x];
            if(solve(x + 1)) return true;
            sides[i] -= matchsticks[x];
        }
        return false;
    }
    return solve();
};
Matchsticks to Square