21xrx.com
2024-11-05 17:29:45 Tuesday
登录
文章检索 我的文章 写文章
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)$,运行速度相对较快,可以用于大规模的数据处理。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复