具有相同时间复杂度的不同行为

Question

我正在 LeetCode 上解决以下问题：

Write a function that takes an integer n and return all possible combinations of its factors. For e.g., 12 should return:
[
   [2, 6],
   [2, 2, 3],
   [3, 4]
]

我想到了以下方法（在 C++ 中）：

class Solution {
public:
    vector<vector<int>> getFactors(int n) {
        if(n==0 || n==1) return vector<vector<int>>();

        vector<vector<int>> result;
        vector<int> factors;
        getFactorsUtil(result, factors, n, 2);

        return result;
    }

    void getFactorsUtil(vector<vector<int>>& result, vector<int>& factors, int n, int start) {
        long int each=1;
        for(int i=0; i<factors.size(); i++)
            each = each*factors[i];
        if(each==n) result.push_back(factors);
        if(each>n) return;

        for(int i=start; i<=n; i++) {
            if(n%i==0) {        //perfectly divisible
                factors.push_back(i);
                getFactorsUtil(result, factors, n, i);
                factors.pop_back();
            }
        }
    }
};

这按预期工作，但在最后一个测试用例上超时：23848713。

其中一个被接受和赞成的解决方案（在 Java 中）如下：

public List<List<Integer>> getFactors(int n) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    helper(result, new ArrayList<Integer>(), n, 2);
    return result;
}

public void helper(List<List<Integer>> result, List<Integer> item, int n, int start){
    if (n <= 1) {
        if (item.size() > 1) {
            result.add(new ArrayList<Integer>(item));
        }
        return;
    }

    for (int i = start; i <= n; ++i) {
        if (n % i == 0) {
            item.add(i);
            helper(result, item, n/i, i);
            item.remove(item.size()-1);
        }
    }
}

两个代码的时间复杂度相同（我认为）。为什么 我的代码 失败而另一个代码运行在 23848713 上成功？我的意思是，我的代码有什么明显的错误，还是在线判断有问题？

感谢您的帮助。

Edit: 之前代码中我的for loop condition中没有<=n（只是因为其他代码有-实际上不需要）根据问题）。我后来把它包括在内。但无论如何，还是会超时。

Edit2：在大 O 表示法中，我们跳过 n 的系数。我认为这就是它在这里中断的原因。我的代码中这些常量的值很大。我想不出其他解释。

Answer 1

因为第一个循环（我在其中计算factors中所有数字的乘积到each），我的代码比O(n)高了一个数量级。由于这个原因，它失败了。

然而，当我用值 n/i（而不是 n）调用它时，我可以通过消除整个循环来完全摆脱 O(n) 因素。之所以如此，是因为我不再需要检查乘积是否等于 n.

因此，由于此更改，代码最终被接受。谢谢。

（发布可能对某人有帮助）。另外，感谢 @user4581301 的提示，最终让我找到它。

具有相同时间复杂度的不同行为

Different behaviors with same time complexity

c++

recursion

backtracking

recursive-backtracking