<p>You are given an integer array <code>matchsticks</code> where <code>matchsticks[i]</code> is the length of the <code>i<sup>th</sup></code> matchstick. You want to use <strong>all the matchsticks</strong> to make one square. You <strong>should not break</strong> any stick, but you can link them up, and each matchstick must be used <strong>exactly one time</strong>.</p>

<p>Return <code>true</code> if you can make this square and <code>false</code> otherwise.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/04/09/matchsticks1-grid.jpg" style="width: 253px; height: 253px;" />
<pre>
<strong>Input:</strong> matchsticks = [1,1,2,2,2]
<strong>Output:</strong> true
<strong>Explanation:</strong> You can form a square with length 2, one side of the square came two sticks with length 1.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> matchsticks = [3,3,3,3,4]
<strong>Output:</strong> false
<strong>Explanation:</strong> You cannot find a way to form a square with all the matchsticks.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= matchsticks.length &lt;= 15</code></li>
	<li><code>1 &lt;= matchsticks[i] &lt;= 10<sup>8</sup></code></li>
</ul>

# upsolve due to TLE
# (Note: seems like a backtracking DFS might have even have not gotten a TLE
# even though it is O(4^N). Important: I think this is because using knapsack
# was the worse possible idea here because N is really small the the value of the
# matchsticks can be really high. E.g. 2^N or even 4^N will not be that great: 
# 2^15 ~= 32k, 4^15 ~= 1 bil, BUT 10**8 is 100 mil, so the max value of the
# knapsack could be 10**8*15/4 ~= 375 mil but then have to scale by n again since
# knapsack is O(NW) so ~5.6 billion (there is also the N^4 part of picking
# combinations) comes down to constants). Wow. This is interesting.
# Wait 2 questions: 1. would it be faster if I just passed in a mask?
# 2. Is the complexity factor of W really valid? how many discrete values can I
# actually reach? It cannot be more than 2^N. So this is good rule of thumb when
# to use knapsack I guess. When W << 2^N. Why does that impact me negatively?
# because now instead of 2^N states in the tree there are N*(W) and if W is
# effectively 2^N it is N*2^N states (that I am trying to cache..) oof. ok
# trying new solution with explicity 2^N states via bitmask.
# AHA Important: Also remember I am creating large lists while the editorial
# solution is not. In total, creation of the entire list will be O(N*2^N) work
# as there at most 2^N items in the list and the tree is of depth N so any item
# in the list could be updated/copied N times. Maybe this only might still work
# because N is so small but I am definitely starting to see why this solution is
# not as nice as the editorial. Avoiding this massive list creation is much more
# elegant. 
# WAIT. But theoretically, now even w/ list creation and knapsack the complexity
# is O(N*2^N) which should still be much better than DFS of O(4^N).
# FIGURED it out. This repeated creation of new lists and copying of lists most
# likely abuses and destroys the caches. While in dfs you do not need to use any
# extra memory at all besides the stack (basically can just use registers and
# stack which probably almost always in cache!!) and when we do DP with a mask and
# sides that is stick far better behaved because now have 3*2^N states but each
# time only storing a VALUE not a new list for every entry :facepalm: which is
# terrible.

# very interesting that there are two camps of runtime solutions. There is a bump 
# around ~4s for dfs / backtracking solutions and another at .2s for dfs w/ pruning
# and the dp caching version? I want to investigate these optimizations more.

# Writing my own dfs solution.
# Checking all four sides times out. Check construction of 3.
# - still times out. :) hahaha.
# - Sorting in reverse order is a pretty big help. I think the intuition
# is if if there is a solution in the tree then examining the large numbers
# of the tree will prune out more possible combinations of matchsticks quickly
# as their combination will be too large of a sum to form a side.
# then use memoization for dfs, as very possible will visit the same node.
# ok so w/ memoization of dfs I am still only in the second hump :).
# there was some mention about optimizing to check if sides are unequal
# - not entirely sure why but when I starting thinking of what optimizations
# to do there is a lot of symmetry in the problem that we can get rid of, and
# I believe this is exactly what it means. Additionally can do function
# coarsening, I believe these optimizations go hand in hand.
# Interestingly, after this, May no longer need caching but we will see.
# tried doing something fancy like making sure

class Solution:
    def makesquare(self, nums) -> bool:
        nums = sorted(nums)[::-1]
        if not nums: return False
        _sum, n = sum(nums), len(nums)
        fourth = _sum // 4
        if fourth != ceil(_sum / 4): return False
        toobig = lambda x: x > fourth
        if any(map(toobig, nums)): return False
        @cache
        def dfs(i: int, *sides: tuple[int]) -> bool:
            if len(list(filter(lambda x: x==fourth, sides))) == 3: return True
            if i >= n or any(map(toobig, sides)): return False
            if nums[i] == 0: return dfs(i+1, *sides) # apparently this exists? should not.
            for j in range(4):
                new_sides = list(sides)
                new_sides[j] += nums[i]
                if dfs(i+1, *(sorted(new_sides)[::-1])): return True
            return False
        return dfs(0, *[0]*4)


# is the solution related to branch-cutting? definitely pruning because if find
# 3 sides know have fourth, but what about the order tree is traversed.. their
# algorithm out of all matchsticks tries to pack the earliest matchstick it can
# into an unformed side. What is the advantage of caching based on BOTH unused
# matchsticks and number of completed sides?

# thought about heaps. but is this just running knapsack 4x making sure to
# always try to pack the larger items first? because if use smallest could
# end up finding a way to pack one bag which will not allow packing other
# bags. But in a sense packing the largest items possible is the most
# restrictive solution, which allows the most flexible solutions with the
# smallest items later.
# Also thought about splitting into 2 and then splitting each into two again
# but this is almost like getting stuck in local minima. And any solutions
# which rely on heaps and replacing items seem complicated, because they involve
# chains of swaps, and those chains look like they could be combinatorial in the
# number of options for swaps.
# Hmm but knapsack tries to maximize while I search for exact.. try to
# rememember problem and see if it applies. Basic idea would be to run knapsack
# to create first match, then update set, run knapsack to create 2nd match,
# update and so on. But say any of the 2nd, 3rd, or 4th, fail, then would have
# to search for another solution in the previous knapsack. So the complexity is
# in the number of solutions? Is there a bound on this? Could it be exponential?
# Because at that point, might just try to run something like knapsack to find
# all solutions and then try to find if there are 4 disjoint ones?
# once I saw sure I was on the right track (above) of using a knapsack-like approach,
# glanced at editorial and saw on totally best track. however, instead of calling it
# knapsack this is bin-packing which is np-complete w/ 4 bins.
# class Solution:
#     def makesquare(self, matchsticks: List[int]) -> bool:
#         n, fourth = len(matchsticks), sum(matchsticks) / 4
#         if fourth != int(fourth): return False
#         if any(matchsticks) > fourth: return False
#         @cache
#         def dp(i, w):
#             if w == fourth: return True, [0]
#             elif i >= n or w > fourth: return False, [0]
#             skip, skip_ans, take, take_ans = *dp(i+1, w), *dp(i+1, w+matchsticks[i])
#             ans = []
#             if skip: ans.extend(skip_ans)
#             if take: ans.extend((1 << i) | ans for ans in take_ans)
#             return (True, ans) if skip or take else (False, [0])
#         # This will TLE, even though it is only O(N^4). 
#         possible, ALL = dp(0, 0)[1], (1 << n)-1
#         if any((reduce(int.__or__, quad, 0) == ALL for quad in combinations(possible, 4))):
#             return True
#         return False
        # This is just incorrect, really what I was looking for was a k-independent set.
        # But those are also NP-hard.
        # possible = [bin(x)[-1:1:-1].ljust(n, "0") for x in dp(0, 0)[1]]
        # g = {i:i for i in range(len(possible))}
        # for i in range(n):
        #     seen = {idx for idx in idxs if possible[idx][i] == "1"}
        #     if len(seen) > 1: idxs -= seen
        # return True if len(idxs) >= 4 else False


33252