使用 DFS 枚举子集

Question

我想枚举给定数组的所有可能子集，总共应该是 2^N。这里我使用总和来表示所有子集，因为在这个例子中总和是不同的。我使用一个名为 taken 的辅助数组来标记当前项目是否被拿走并进行 DFS。这是代码：

void dfs(vector<int>& res, vector<int>& nums, vector<bool>& taken, int sum, int pos) {
    for (int i = pos; i < nums.size(); ++i) {
        if (!taken[i]) {
            taken[i] = true;
            res.push_back(nums[i] + sum);
            dfs(res, nums, taken, sum + nums[i], pos + 1);
            taken[i] = false;
        }
    }
    return;
}
int main() {
    vector<int> test = {1, 10, 100, 1000};
    vector<bool> t(4, false);
    vector<int> res;
    dfs(res, test, t, 0, 0);
    return 0;
}

但是这段代码并没有return 2^n 的结果。

Answer 1

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);
    }
}

这将遍历大小最大为 63 的向量（如果您的 unsigned long long 是 64 位）。可能应该重新考虑任何更大的向量，因为这需要一段时间，因为这是 O(2^n)，正如您所指出的。

基本上 unsigned long long i 的每一位代表 nums 中的一个位置，是否应该将其添加到总和中。

Answer 2

我已经修复了你的代码

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;
}

并且由于您不向后访问元素（即已经添加的索引），因此您不必维护一个数组来检查是否已访问。

使用 DFS 枚举子集

Enumerate subsets with DFS

c++

algorithm

enumeration

subset

depth-first-search