Leetcode-78 Subsets

发表于 | 分类于 | 次

Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example 1

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解题思路

回溯法。从前往后挑选元素，每次挑选有多个选择。为防止重复，在每次挑选元素后，下次挑选只能选择该元素之后的那些元素。例如，在挑选 2 后，下一次挑选只有 3 这一个选择。

复杂度分析

  • 时间复杂度：$O(2^n)$，总共有这么多个元素。
  • 空间复杂度：$O(n)$，不包含返回结果时所占用的空间。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
	vector<vector<int>> subsets(vector<int>& nums) {
		vector<int> sol;
		help(nums, sol, 0);
		return res;
	}

private:
	vector<vector<int>> res;

	void help(vector<int> &nums, vector<int> &sol, int k) {
		res.push_back(sol);
		for (int i = k; i < nums.size(); ++i) {
			sol.push_back(nums[i]);
			help(nums, sol, i + 1);
			sol.pop_back();
		}
	}
};