monre's questions

以下是一道 Leetcode 题目：473.火柴到正方形（https://leetcode.com/problems/matchsticks-to-square/description/）

问题陈述

你有大小为n的数组matchsticks，每个数组包含不同的火柴长度。你想用所有火柴拼成一个正方形，但不能折断它们。如果可以，返回true。如果不能，返回false。

示例 1：

• 输入：火柴= [1,1,2,2,2]

• 输出：true

• 解释：你可以拼出一个长度为 2 的正方形，正方形的一边有两根长度为 1 的木棍。

示例 2：

• 输入：火柴= [3,3,3,3,4]

• 输出：false

• 解释：你无法找到用所有火柴组成一个正方形的方法。

限制：

• 1 <= n <= 15

• 1 <=火柴[i] <= 10^8

我见过这个问题的 O(4^n) 和 O(n*2^n) 解决方案。我通过一种在其他地方没有见过的解决方案以不同的方式解决了这个问题，我不确定它的时间复杂度是多少。我将使用matchsticks = [4, 4, 4, 3, 1] -> sideLength = 4的示例来解释解决方案。我用 C++ 解决了它。代码在最后：

我的解决方案：对于每一侧，遍历火柴棒数组，并针对每根火柴棒探索两个决策：将其添加到当前侧，不将其添加到当前侧。完成一侧后，转到下一侧，从头开始对火柴棒数组进行迭代（i=0）。由于每个元素有两个决策，我最初想说时间复杂度是 O(2^n)。整棵树的高度实际上不是n，但各个子树的高度最多是 n 。我在这里有点困惑。如何确定这种回溯解决方案的时间复杂度？

代码：

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;
    }
};