C++求解三的幂子集问题大输入触发SIGSEGV错误原因问询

直接原因：栈溢出 #

你代码中使用了C++标准未定义的栈上变长数组（VLA）：ll a[n];和ll idx[n] = {0};都是以输入的变量n作为数组长度，这类编译器扩展语法实现的数组默认分配在程序栈空间，而常规程序栈的容量通常只有2~8MB。当输入的n值较大时，两个long long类型数组占用的内存会迅速超过栈容量，触发栈溢出，最终抛出SIGSEGV错误。

根本原因：逻辑设计冗余 #

这道题的核心规律是：按子集和从小到大排序后的第n个子集，正好对应n的二进制表示中所有为1的位，每一位对应3的对应次幂。比如n=5（二进制101），对应的子集就是$3^0 + 3^2 = 1+9=10$，你根本不需要申请长度为n的数组，最多只需要遍历n的二进制位（最多60位，对应long long的长度），完全不需要大内存空间。你申请长度为n的数组属于完全多余的操作，n稍大就必然触发内存错误。

其他潜在问题 #

代码中n & (1<<j)里的1是int类型，当j超过31时左移操作会溢出，行为未定义，需要改成1LL << j才能适配long long类型的n。

修复示例片段 #

while(t--){
    ll n;
    cin >> n;
    vector<ll> res;
    // long long最多63位，遍历到60足够覆盖常规题目输入范围
    for(ll j=0; j<=60; j++){ 
        if(n & (1LL << j)){
            res.push_back(poww(3, j));
        }
    }
    cout << res.size() << endl;
    for(auto num : res){
        cout << num << " ";
    }
    cout << endl;
}

内容的提问来源于stack exchange，提问作者tanya chhabra