使用DFS枚举子集

我已经修复了你的代码

void dfs(vector<int>& res, vector<int>& nums,  int sum, int pos) {

    for (int i = pos; i < nums.size(); ++i) {
        res.push_back(sum + nums[i]);
        dfs(res, nums,  sum + nums[i], i + 1); // i + 1 instead of pos + 1
    }
    return;
}
int main() {
    vector<int> test = {1, 2, 3};
    vector<int> res;
    dfs(res,test,0, 0);
    cout << res.size() << endl;
    copy(res.begin(), res.end(), ostream_iterator<int>(cout , " "));
    cout <<endl;
    return 0;
} 

由于您不向后访问元素(即已添加的索引),因此不必维护数组来检查访问的元素。

void enumerate_all_subsets(vector <int> &res, const vector <int> &nums) {
    if(nums.empty()) return;
    for(auto i = 0ull; i < (1 << nums.size()); ++ i) {
        int sum = 0;
        for(auto k = 0; k < nums.size(); ++ k)
            if((i >> k) & 1)
                sum += nums[k];
        res.push_back(sum);
    }
}

O(2^n) ,正如你所说。

基本上每一位 unsigned long long i 表示中的位置 nums 以及是否应将其添加到总和中。