子集

描述

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这道题目可以使用回溯算法来解决。在回溯算法中，我们需要维护一个路径（path），表示当前已经选了哪些数，以及一个选择列表（choices），表示当前还可以选择哪些数。在每一步中，我们可以选择将一个数加入路径中，或者不将其加入路径中。当路径中的数的个数达到了数组的长度时，我们就得到了一个新的子集。

具体实现：

我们可以使用两个函数来解决这个问题。一个函数是 backtrack，它用于搜索所有可能的子集；另一个函数是 subsets，它用于初始化回溯算法，并返回所有可能的子集。

在 backtrack 函数中，我们首先将当前路径加入到结果集中。然后，我们遍历当前的选择列表，对于每个选择，我们将其加入到路径中，并递归调用 backtrack 函数。递归完成后，我们需要将该选择从路径中删除，以便进行下一次选择。

在 subsets 函数中，我们首先初始化结果集为空集。然后，我们调用 backtrack 函数，得到所有可能的子集，并返回结果集。

C++代码

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res; // 初始化结果集为空
        vector<int> path; // 初始化路径为空
        backtrack(nums, 0, path, res); // 调用 backtrack 函数
        return res; // 返回结果集
    }

    void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) {
        res.push_back(path); // 将当前路径加入到结果集中
        for (int i = start; i < nums.size(); i++) { // 遍历当前的选择列表
            path.push_back(nums[i]); // 将选择加入到路径中
            backtrack(nums, i + 1, path, res); // 递归调用 backtrack 函数
            path.pop_back(); // 将该选择从路径中删除
        }
    }
};

Python代码

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [] # 初始化结果集为空
        path = [] # 初始化路径为空
        self.backtrack(nums, 0, path, res) # 调用 backtrack 函数
        return res # 返回结果集

    def backtrack(self, nums, start, path, res):
        res.append(path[:]) # 将当前路径加入到结果集中
        for i in range(start, len(nums)): # 遍历当前的选择列表
            path.append(nums[i]) # 将选择加入到路径中
            self.backtrack(nums, i + 1, path, res) # 递归调用 backtrack 函数
            path.pop() # 将该选择从路径中删除