0%

[Leetcode]78. Subsets(C++)

题目描述

题目链接:78. Subsets

Given an integer array nums, return all possible subsets (the power set).

The solution set must not contain duplicate subsets.

例子

例子 1

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

例子 2

Input: nums = [0]
Output: [[],[0]]

Constraints

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10

解题思路

这道题是很典型的需要使用回溯方法的题目,非常适合用来理解回溯的思路和做法。回溯法简单来说就是暴力遍历所有可能性,并且在有需要的情况下按照要求筛选出其中的某一部分。时间复杂度通常来说是指数级别的(在某些情况下可以理解一些条件进行剪枝降低时间),由于时间复杂度非常高,所以需要用回溯法的题目数据规模一般不会很大。例如本题中的数组的长度最多只有 10,所以在看到数据规模较小时可以考虑是不是需要用回溯解题。

回溯做法通常是在循环使用深度优先搜索,循环的目的是遍历当前状态下的所有下一步可能性,而深度优先搜索则是对下一步也进行通常操作,因此可以遍历所有情况。

具体到这道题而言,做法如下:

  • 初始化当前子集为空,并传递当前子集 subset 和起始索引 idx(0)给 DFS 函数:
  • DFS 函数中:
    • 如果索引已经到达数组尾端,表示目前情况下已经遍历了所有组合,所以将当前子集 subset 放入结果数组 result 中并返回
    • 否则在数组中进行循环,索引从 idx 到数组末尾:
      • subset 中放入数组当前元素 nums[i]
      • 递归调用 DFS, 传入 subset, i + 1 ,表示在遍历包括 nums[i] 之后的所有情况
      • DFS 返回后,将 subset 末尾元素 (nums[i]) 弹出,重置当前状态,并进入循环下一位置进行重复操作
  • 最后 result 即为所需结果

这里注意一下,经过试验,题目中的 The solution set must not contain duplicate subsets. 应该隐含了输入数组中不包含重复数字,或者指的是数组中同一位置只能选择一次,而不是指子集不能完全相同,因此:

  • 假如输入是 [1,1],满足要求的子集应该有:
    • [] 一个都不选
    • [1] 选第一个元素
    • [1] 选第二个元素
    • [1,1] 选两个元素

代码如下:

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
#include <algorithm>
#include <vector>

class Solution {
public:
std::vector<std::vector<int>> subsets(std::vector<int>& nums) {
std::vector<int> subset;
std::vector<std::vector<int>> result;

dfs(nums, 0, subset, result);
return result;
}

private:
void dfs(const std::vector<int>& nums, size_t idx, std::vector<int>& subset,
std::vector<std::vector<int>>& result) {
result.push_back(subset);
if (idx >= nums.size()) {
return;
}

for (int i = idx; i < nums.size(); ++i) {
subset.push_back(nums[i]);
dfs(nums, i + 1, subset, result);
subset.pop_back();
}
}
};
  • 时间复杂度: O(2^n)
  • 空间复杂度: O(n)

GitHub 代码同步地址: 78.Subsets.cpp

其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions