Keshawn_lu's Blog

Leetcode 78. 子集

字数统计: 183阅读时长: 1 min
2020/09/20 Share

题目简介:

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

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: 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
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:

vector<vector<int>> res;

void dfs(vector<int>& nums, vector<int>& temp, int pos){

res.push_back(temp);

for(int i = pos; i < nums.size(); i++){

temp.push_back(nums[i]);

dfs(nums, temp, i + 1); //pos = i + 1

temp.pop_back();
}
}

vector<vector<int>> subsets(vector<int>& nums) {

vector<int> temp;

dfs(nums, temp, 0);

return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: