[Leetcode]78. Subsets(C++)

题目描述

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] 选两个元素

代码如下：

#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