LeetCode刷题（173）～子集【迭代｜回溯｜遍历】

题目描述

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

解答 By 海轰

提交代码（迭代）

vector<vector<int>> subsets(vector<int>& nums) { int n=nums.size(); vector<int> a; vector<vector<int> > ans; for(int i=0;i<(1<<n);++i) { a.clear(); for(int j=0;j<n;++j) { if(i & (1 << j)) a.push_back(nums[j]); } ans.push_back(a); } return ans; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

运行结果

提交代码（递归 回溯）

vector<int> t; vector<vector<int>> ans; void dfs(int cur, vector<int>& nums) { if (cur == nums.size()) { ans.push_back(t); return; } // 选择当前元素 t.push_back(nums[cur]); dfs(cur + 1, nums); t.pop_back(); // 不选择当前元素 dfs(cur + 1, nums); } vector<vector<int>> subsets(vector<int>& nums) { dfs(0, nums); return ans; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

运行结果

回溯代码模版

vector<int> t;
void dfs(int cur, int n) { if (cur == n) { // 记录答案 // ... return; } // 考虑选择当前位置 t.push_back(cur); dfs(cur + 1, n, k); t.pop_back(); // 考虑不选择当前位置 dfs(cur + 1, n, k);
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
 

提交代码（遍历）

 //可以直接遍历，遇到一个数就把所有子集加上该数组成新的子集，遍历完毕即是所有子集 vector<vector<int>> subsets(vector<int>& nums) { if(nums.empty()) return vector<vector<int>>(); vector<vector<int>> res; res.push_back({}); for(auto num : nums) { vector<vector<int>> state = res; for(auto r : res) { r.push_back(num); state.push_back(r); } res = state; } return res; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108689880