LeetCode 473：火柴拼正方形回溯解法的时间复杂度分析

题目描述 #

给定长度为n的火柴长度数组matchsticks，需要使用所有火柴拼成正方形（不可折断火柴），若能拼成则返回true，否则返回false。

示例1 #

• 输入：matchsticks = [1,1,2,2,2]
• 输出：true
• 解释：可拼成边长为2的正方形，其中一条边由两根长度为1的火柴组成。

示例2 #

• 输入：matchsticks = [3,3,3,3,4]
• 输出：false
• 解释：无法使用所有火柴拼成正方形。

约束条件 #

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

我的解法与疑问 #

我见过这道题的O(4^n)和O(n*2^n)复杂度解法，但自己提出了一种没见过的回溯解法，不确定它的时间复杂度。下面以matchsticks = [4,4,4,3,1]（边长为4）为例说明解法思路，代码附后：

解法思路：针对每条边遍历火柴数组，对每个火柴做两种选择：加入当前边或不加入。当一条边构建完成后，转向下一条边并重新从数组开头遍历。因为每个元素有两种选择，我最初认为复杂度是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;
    }
};

内容的提问来源于stack exchange，提问作者monre