Нахождение временной сложности решения с возвратом для генерации проблемы всего подмножества

Учитывая проблему различных целых чисел, сгенерируйте все подмножества. 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), решив указанное выше рекуррентное соотношение.

Но со вторым решением я не могу определить отношение повторения, чтобы, наконец, использовать обратную замену, чтобы получить временную сложность, и не могу получить его методом дерева повторения. Пожалуйста, помогите мне найти временную сложность второго решения.