21xrx.com
2025-03-26 14:56:43 Wednesday
文章检索 我的文章 写文章
C++递归实现求所有子集
2023-07-04 19:07:57 深夜i     --     --
C++ 递归 子集 实现

在计算机编程中，递归是一种常用的编程技巧。递归的基本思想是将一个大问题拆分成一些小问题来解决，从而简化问题的复杂性。在C++中，递归可以用于求解所有子集这一问题。

求解所有子集的问题可以用递归来实现。具体实现方法是：首先将原集合分为两部分，一部分是原集合的第一个元素，另一部分是除第一个元素以外的其他元素。然后分别对这两个部分进行递归处理，最终得到所有子集的解。

下面是C++代码的实现：

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> subsets(vector<int>& nums) {
  vector<vector<int>> res;
  vector<int> cur;
  helper(res, cur, nums, 0);
  return res;
}
void helper(vector<vector<int>>& res, vector<int>& cur, vector<int>& nums, int start) {
  res.push_back(cur);
  for (int i = start; i < nums.size(); i++) {
    cur.push_back(nums[i]);
    helper(res, cur, nums, i + 1);
    cur.pop_back();
  }
}
int main() {
  vector<int> nums = 2;
  vector<vector<int>> res = subsets(nums);
  for (vector<int> v : res) {
    cout << "[";
    for (int i : v)
      cout << i << " ";
    
    cout << "]" << endl;
  }
  return 0;
}

代码中的 `subsets` 函数是递归函数的入口。首先声明了一个空的结果集 `res` 和一个空的子集 `cur`。然后通过调用 `helper` 函数对 `res` 和 `cur` 进行填充。`helper` 函数的作用是：将所有以 `cur` 开头的子集添加到 `res` 中，同时从 `nums[start]` 开始对余下的部分进行递归处理。

最终对 `res` 进行输出，即可得到所有子集的结果。

C++递归实现求所有子集的思想简单，代码易于理解。此外，该方法的时间复杂度为 $O(2^n)$，空间复杂度为 $O(n)$，运行速度相对较快，可以用于大规模的数据处理。

  
  

评论区