bfs解决子集和数c++代码

以下是使用 BFS 算法解决子集和问题的 C++ 代码示例：

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

bool subset_sum_bfs(vector<int>& nums, int target) {
    int n = nums.size();
    queue<pair<int, int>> q;  // (index, current_sum)
    q.push({0, 0});
    while (!q.empty()) {
        auto [index, current_sum] = q.front();
        q.pop();
        if (current_sum == target) {
            return true;
        }
        if (index == n) {
            continue;
        }
        q.push({index + 1, current_sum + nums[index]});
        q.push({index + 1, current_sum});
    }
    return false;
}

// 示例用法
int main() {
    vector<int> nums = {3, 34, 4, 12, 5, 2};
    int target = 9;
    cout << (subset_sum_bfs(nums, target) ? "True" : "False") << endl;  // 输出 True
    return 0;
}

这段代码与 Python 版本的代码非常类似，只是语法不同。在 C++ 中，我们使用了 `std::queue` 来保存搜索过程中的状态，每个状态使用一个 `std::pair` 来表示，第一个元素表示当前搜索到的数的下标，第二个元素表示当前已经选择的数的和。初始状态为 `(0, 0)`，表示还没有选择任何数，当前和为 0。然后我们每次从队列中取出一个状态，根据这个状态可以分为两种情况：

1. 将当前数加入当前和中，得到一个新的状态 `{index + 1, current_sum + nums[index]}`，将其加入队列。
2. 不将当前数加入当前和中，得到一个新的状态 `{index + 1, current_sum}`，将其加入队列。

这样一直搜索下去，直到队列为空或者找到了一个符合条件的状态，即当前和等于目标值。如果搜索完整个数组都没有找到符合条件的状态，则返回 False。

需要注意的是，这种方法的时间复杂度为 $O(2^n)$，其中 $n$ 为数组的长度。因此，在实际应用中，当 $n$ 比较大时，可能需要采用其他更高效的算法来解决子集和问题。