找到生成所有子集问题的回溯解决方案的时间复杂度

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) 通过求解上述递归关系。

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

Answer 1

问题2的类推关系为：

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

– 从 current 到 A.size() 的 for 循环之后。要解决这个问题，请展开第一项：

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).

找到生成所有子集问题的回溯解决方案的时间复杂度

finding time complexity of backtracking solution for generate all subset problem

recursion

time-complexity

subset

backtracking

recurrence