寻找生成所有子集问题的回溯解的时间复杂度

Question

给定不同整数的问题，生成所有子集。https://www.interviewbit.com/problems/subset/

我找到了两种解决方案。

第一个解决方案::

 void helper_subsets(vector<vector<int>> &res , vector<int> &A , 
    vector<int> &subset ,int current)
{
    if(current == A.size())
        res.push_back(subset) ;
    else
    {
        helper_subsets(res,A,subset,current+1) ;
        subset.push_back(A[current]) ;
        helper_subsets(res,A,subset,current+1) ;
        subset.pop_back() ;
    }
}

vector<vector<int> >subsets(vector<int> &A) {
    vector<vector<int>> res ;

    sort(A.begin(),A.end()) ;

    vector<int> subset ;

    helper_subsets(res , A , subset , 0 ) ;

    sort(res.begin(),res.end()) ;
    return res ;
}

第二种解决方案：

void helper_subsets(vector<vector<int>> &res , vector<int> &A , 
    vector<int> &subset ,int current)
{
    res.push_back(subset) ;
    for(int i = current ; i < A.size() ; i++)
    {
        subset.push_back(A[i]) ;
        helper_subsets(res,A,subset,i+1) ;
        subset.pop_back() ;
    }
}

vector<vector<int> > subsets(vector<int> &A) {
    vector<vector<int>> res ;

    sort(A.begin(),A.end()) ;

    vector<int> subset ;

    helper_subsets(res , A , subset , 0 ) ;

    sort(res.begin(),res.end()) ;
    return res ;
}

t（n）=2t（n-1）c（即2个大小为n-1的递归调用，每个n都有一些恒定的时间）t（n）=O（2^n）通过解决上述递归关系。

但对于第二个解，我无法定义递归关系以最终使用反向替换来获得时间复杂度，并且无法通过递归树方法获得时间复杂度。请帮我找到第二个解的时间复杂度。

Answer 1

问题2的类似递归关系为：

       n - 1
T(n) =   Σ  T(n - i) + c
       i = 1

–从当前到A.size（）的循环。要解决此问题，请展开第一项：

T(n) = T(n - 1) + T(n - 2) + T(n - 3) + ... + T(1) + c
       --------
           |
     =     |      T(n - 2) + T(n - 3) + ... + T(1) + c +
            --->  T(n - 2) + T(n - 3) + ... + T(1) + c

     = 2 * [T(n - 2) + T(n - 3) + ... + T(1) + c]
     = 2 * T(n - 1)

即，一个非常相似的递归关系，仅相差一个常数。它仍然计算为O（2^n），基本情况为T（1）=O（1）。