algorithm - 如何计算回溯的空间复杂度？

问题描述
什么是计算回溯算法的空间（栈空间）和时间复杂度的好方法？
例子
我们希望输出组合的长度正好是K，并且sol集必须是唯一的
输入：
阿瑞：[1,2,3,4,5]
K:4分
输出：
[1,2,3,4]//[2,1,3,4]无效，因为它的==[1,2,3,4]
[1,2,3,5]
[1,3,4,5]
[2,3,4,5]

// arr == [1,2,3,4,5]
// K   == 4
// backtrack(arr,4,0,{},...other params we don't care)

void backtrack(vector<int> &arr, int K, int start, vector<int> &sol, ...)
{
     if(sol.size() == K)
     {
         //...
     }
     else
     {
           for(int i = start; i < arr.size(); i++)
           {
              sol.push_back(arr[i]);
              backtrack(arr, K, i+1,sol,...);
              sol.pop_back();
           }
     }
}

我想
最差的空间复杂度是O（k），因为我想当我再返回f1（）时，f2（）到f5（）不会在f1（）的整个子树完成后被调用。

                   []
      f1()    f2() f3() f4() f()5
f1.1() f()1.2 ...

最坏的时间复杂度是O（n^ k），其中n是数组的长度。

最佳答案

技术上的时间复杂度不是O（n^ k），而是O（从i＝1到k bin（n，i）），因为你不从ARR的开始开始搜索，而是从最后一个元素后面的元素开始搜索，并且也不切断像“cc>”那样无法完成的状态。通常情况下，这种情况下的时间复杂度是指从一种状态到另一种状态所需的平均时间。

关于algorithm - 如何计算回溯的空间复杂度？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57379531/