代码之家 › 专栏 › 技术社区 › ssd

使用DFS枚举子集

depth-first-search enumeration subset algorithm c++

-1

ssd · 技术社区 · 8 年前

我想枚举给定数组的所有可能子集,总共应该是2^N。在这里,我使用sum来表示所有子集,因为在本例中,sum是不同的。我使用一个名为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;
}

但该代码不会在结果中返回2^n个结果。

2 回复 | 直到 8 年前

1

2

thebenman 8 年前

我已经修复了你的代码

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

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

2

1

N00byEdge 8 年前

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 以及是否应将其添加到总和中。