Чем битовый набор отличается от битовой маски из-за сложности времени?

Question

Задача

Учитывая массив из N элементов, проверьте, можно ли получить сумму S, выбрав некоторые (или ни один) элементы массива и добавив их.

с использованием битов

#include<bits/stdc++.h>
using namespace std;
bitset<1000000+10> bit;
int a[100];
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int s;
    cin>>s;
    bit[0]=1;
    for(int i=0;i<n;i++){
        bit|=bit<<a[i];
    }
    if(bit[s]){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}

Использование битовой маски

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int t;cin>>t;
    while(t--){
        int n; cin>>n; int a[n+5];
        for(int i=0;i<n;i++) cin>>a[i];
        int s,i,j; cin>>s;
        for(i=0;i<(1<<n);i++){
            int x=0;
            for(j=0;j<n;j++){
                if(i & (1<<j)) x+=a[j];
            }
            if(x==s){
                cout<<"YES\n"; break;
            }
        }
        if(i==(1<<n)) {cout<<"NO\n";}

    }

    return 0;
}

Однако я знаю, что сложность времени здесь хорошо видна O (2 ^ n * n)

1) Но когда мы говорим о наборе битов, это может выглядеть как O (n * max (a [i])) Я говорю это, потому что, если мы рассмотрим сдвиг битов в битах, это O (n) тогда для максимального значения элемента массива нам, возможно, придется сдвинуть 10 ^ 6 бит в битах (не уверен в сложности времени побитовых операций на битах)

2) Но битовая маска не будет работать для более чем 64 чисел в массиве, с другой стороны, мы можем хранить 10 ^ 6 чисел в наборе битов (не уверен насчет диапазона набора битов)

Пожалуйста, исправьте, если я ошибаюсь в двух вышеприведенных утверждениях.

Из чего можно сделать вывод, что набор битов более эффективен, чем битовая маска?