C++回溯法求解子集合问题

子集合问题可以用回溯法来求解。回溯法是一种暴力搜索算法，通过不断地尝试所有可能的解，最终得到问题的解。

以下是用C++实现子集合问题的回溯法：

#include <iostream>
#include <vector>

using namespace std;

void backtrack(vector<int>& nums, vector<int>& path, vector<vector<int>>& res, int start) {
    res.push_back(path);  // 将当前路径加入结果集

    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);  // 将当前元素加入路径
        backtrack(nums, path, res, i + 1);  // 递归处理下一个元素
        path.pop_back();  // 回溯，将当前元素从路径中删除
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> res;
    vector<int> path;
    backtrack(nums, path, res, 0);
    return res;
}

int main() {
    vector<int> nums {1, 2, 3};
    vector<vector<int>> res = subsets(nums);
    for (auto& r : res) {
        for (auto& num : r) {
            cout << num << " ";
        }
        cout << endl;
    }
    return 0;
}

在回溯函数`backtrack`中，首先将当前路径加入结果集，然后从start位置开始循环，将当前元素加入路径，递归处理下一个元素，最后回溯，将当前元素从路径中删除。在主函数中调用`subsets`函数即可得到所有的子集合。

以上代码的时间复杂度为O(2^n)，因为这是一个指数级别的问题，需要枚举所有可能的解。