Time Complexity of Backtracking solution to Leetcode 473. Matchsticks to Square

Question

The following is a Leetcode problem: 473. Matchsticks to Square (https://leetcode.com/problems/matchsticks-to-square/description/)

---

Problem Statement

You have an array, matchsticks, of size n, with different matchstick lengths. You want to create a square using all the matchsticks, without breaking them. If you can, return true. If you can't, return false.

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 <= n <= 15

• 1 <= matchsticks[i] <= 10^8

---

I have seen two different solutions to this problem. I have solved the problem through a third solution that I haven't seen anywhere else, and I am not sure what its time complexity is. I will explain my solution first, and then the other two solutions, since I also have a question about the last one of them. I will explain the solutions with the example matchsticks = [4, 4, 4, 3, 1] -> sideLength = 4. I solved them in C++. The code for all three is at the end:

1. My solution: For each side, iterate through the matchsticks array, and for each matchstick explore both decisions: add it to the current side, and not add it to the current side. Once a side is complete, move on to the next side, starting the iteration over the matchsticks array from the beginning (i=0). Since there are two decisions per element, I was initially tempted to say that the time complexity is O(2^n). The height of the entire tree is not really n, but the height of individual subtrees is, at most. I am a bit confused here.

The main two solutions I have seen online:

2. Each matchstick has to go on one of the 4 sides. Hence, we try all configurations. Since for each matchstick we try placing it on all 4 sides and backtracking when we fail to create a square, we have a decision tree with 4 branches per matchstick -> time complexity: O(4^n). This is clear. We can theoretically apply memoization to this problem since on different branches we can end up at the same matchstick configuration for a specific matchstick at index i. So if we know that it didn't work the first time, we can re-use that knowledge. But then our tracked variables are a side configuration (vector(4)), and an index (int), and we end up having something like a map<vector, int>, which is not super efficient.

3. As we have four sides from the square to complete, we can start with the first side, place matchsticks until we complete the side, and continue with the next sides until we complete the square. How? At each step, we choose from all the matchsticks that we haven't used so far, keeping track of which we have. We can also apply memoization here, where this time our tracked variables are the available/used matchsticks, and the number of sides which have been completed. Since the problem states that n is constraint such that it is <= 15, we can use a bitmask (eg a 16-bit or 32-bit integer) to keep track of the available/used matchsticks, and an int to keep track of the completed sides. The total possible variations, and hence the total number of branches, are therefore 4 * 2^n. For each branch we iterate through all matchsticks, and hence the total time complexity is O(n * 2^n). -- Bonus question: without memoization, is the time complexity of this solution O(n^n)? I thought so originally, but I see elsewhere that it is still O(n * 2^n), and I don't really understand why.

---

The following is the code for the three solutions, in C++ - descending sorting added to make the matchstick placement tries more efficient. Memoization has been removed from the first two to simplify the code:

My solution, 1:

class Solution {
public:
    bool makesquare(const std::vector<int>& matchsticks) {
        int sum = 0;
        for(int m : matchsticks)
            sum += m;

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

        int sideLength = sum / 4;
        std::vector<bool> available(matchsticks.size(), true);
        return dfs(matchsticks, sideLength, 0, 0, available, 4);
    }

    bool dfs(const std::vector<int>& matchsticks, int sideLength, int currSideLength, int i, std::vector<bool>& available, int numRemainingSides) {
        if(currSideLength == sideLength) {
            currSideLength = 0;
            numRemainingSides --;
            i = 0;  // restart choice of matches
            if(numRemainingSides == 0)
                return true;
        }
        if(i == matchsticks.size())
            return false;

        if(available[i]) {
            // take current matchstick for the current side
            available[i] = false;
            if(dfs(matchsticks, sideLength, currSideLength + matchsticks[i], i+1, available, numRemainingSides))
                return true;
            // do not take the current matchstick for the current side
            available[i] = true;
        }
        if(dfs(matchsticks, sideLength, currSideLength, i+1, available, numRemainingSides))
            return true;

        return false;
    }
};

Solution 2:

class Solution {
public:
    bool makesquare(const std::vector<int>& matchsticks) {
        int sum = 0;
        for(int m : matchsticks)
            sum += m;

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

        std::sort(matchsticks.rbegin(), matchsticks.rend());

        int sideLength = sum / 4;
        std::vector<int> sides(4, sideLength);
        return dfs(matchsticks, sides, 0);
    }

    bool dfs(const std::vector<int>& matchsticks, std::vector<int>& sides, int idx) {
        if(idx == matchsticks.size())
            return true;

        for(int i=0; i<4; i++) {
            if(sides[i] - matchsticks[idx] >= 0) {
                sides[i] -= matchsticks[idx];
                if(dfs(matchsticks, sides, idx+1))
                    return true;
                // backtrack
                sides[i] += matchsticks[idx];
            }
        }

        return false;
    }
};

---

Solution 3:

class Solution {
public:
    bool makesquare(const std::vector<int>& matchsticks) {
        int sum = 0;
        for(int m : matchsticks)
            sum += m;

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

        int sideLength = sum / 4;
        int available = (1 << matchsticks.size()) - 1;  // all matchsticks available
        return dfs(matchsticks, sideLength, 0, available, 0);
    }

    bool dfs(const std::vector<int>& matchsticks, int sideLength, int currentSideLength, int available, int completedSides) {
        if(available == 0)
            return true;

        if(currentSideLength == sideLength) {
            currentSideLength = 0;
            completedSides ++;
        }
        
        for(int i=0; i<matchsticks.size(); i++) {
            if((available & (1 << i)) && matchsticks[i] + currentSideLength <= sideLength) {
                if(dfs(matchsticks, sideLength, matchsticks[i] + currentSideLength, available - (1 << i), completedSides))
                    return true;
            }
        }

        return false;
    }
};

---

Answer 1

Complexity of your solution:
The worst-case scenario you would face when you need to add $O(n)$ number of matchsticks (say $n-3$) to obtain one side. Your tree will be of height $O(n)$ in that case. The rest, in my opinion, is straight forward from here.

Complexity of your solution 3:
The height of the tree is at most $n$, there is at most $O(n)$ amount of work done at each node. As specified, "...we can start with the first side, place matchsticks until we complete the side..." there is only binary choice for each matchstick for the given side. Making the total complexity $O(n\cdot2^n)$.

Also, I do not find any major difference between your solution and solution 3.