19071 递归实现指数型枚举

### 思路
1. 使用递归实现指数型枚举。
2. 在每一步中都有两种选择：选中当前元素或不选中当前元素。
3. 递归遍历所有可能的选择方案。
4. 使用一个集合来存储所有可能的和，避免重复。
5. 最后将集合中的所有和按字典序输出。

### 伪代码
1. 定义一个函数 `dfs(index, current_sum)`：
   - 如果 `index` 等于 `n`，且 `current_sum` 不为 0，将 `current_sum` 添加到结果集合中。
   - 否则：
     - 递归调用 `dfs(index + 1, current_sum + arr[index])`（选择当前元素）。
     - 递归调用 `dfs(index + 1, current_sum)`（不选择当前元素）。
2. 在主函数中：
   - 读取输入，初始化数组 `arr` 和结果集合 `result_set`。
   - 调用 `dfs(0, 0)`。
   - 将 `result_set` 转换为列表并排序。
   - 输出结果。

### C++代码

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

void dfs(int index, int current_sum, const vector<int>& arr, set<int>& result_set) {
    if (index == arr.size()) {
        if (current_sum != 0) {
            result_set.insert(current_sum);
        }
        return;
    }
    // 选择当前元素
    dfs(index + 1, current_sum + arr[index], arr, result_set);
    // 不选择当前元素
    dfs(index + 1, current_sum, arr, result_set);
}

int main() {
    int n;
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    set<int> result_set;
    dfs(0, 0, arr, result_set);

    vector<int> result(result_set.begin(), result_set.end());
    sort(result.begin(), result.end());

    for (int sum : result) {
        cout << sum << endl;
    }

    return 0;
}

### 总结
- 使用递归实现指数型枚举，在每一步中都有两种选择：选中当前元素或不选中当前元素。
- 使用集合来存储所有可能的和，避免重复。
- 最后将集合中的所有和按字典序输出。

原文地址：https://blog.csdn.net/huang1xiao1sheng/article/details/142978606

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！