鱼C论坛

 找回密码
 立即注册
查看: 1312|回复: 0

C++刷leetcode(78. 子集)【回溯】

[复制链接]
发表于 2020-4-12 11:19:52 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 糖逗 于 2020-6-14 15:51 编辑

题目描述:
  1. 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

  2. 说明:解集不能包含重复的子集。

  3. 示例:

  4. 输入: nums = [1,2,3]
  5. 输出:
  6. [
  7.   [3],
  8.   [1],
  9.   [2],
  10.   [1,2,3],
  11.   [1,3],
  12.   [2,3],
  13.   [1,2],
  14.   []
  15. ]

  16. 来源:力扣(LeetCode)
  17. 链接:https://leetcode-cn.com/problems/subsets
  18. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码



  1. #include <iostream>
  2. #include <vector>


  3. using namespace std;


  4. void dfs(vector<int>&input, int start, vector<int>&temp, vector<vector<int> >& res){
  5.         if(start >= input.size()) return;
  6.         temp.push_back(input[start]);
  7.     res.push_back(temp);
  8.         dfs(input, start + 1, temp, res);
  9.         temp.pop_back();
  10.     dfs(input, start + 1, temp, res);
  11. }

  12. vector<vector<int>> solution(vector<int>& input) {
  13.         vector<vector<int> > res;
  14.         vector<int> temp;
  15.         dfs(input, 0, temp, res);
  16.         res.push_back(vector<int>(0));
  17.         return res;
  18. }



  19. int main(void){
  20.         int number;
  21.         vector<int> input;
  22.         while(cin >> number){
  23.                 input.push_back(number);
  24.         }
  25.         vector<vector<int> > res = solution(input);
  26.         for(int i = 0; i < res.size(); i++){
  27.                 for(int j = 0; j < res[i].size(); j++){
  28.                         cout << res[i][j] << " ";
  29.                 }
  30.                 cout << endl;
  31.         }
  32.        
  33.        
  34.         return 0;
  35. }
复制代码



注意事项:
1.回溯算法

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-3 12:09

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表