# 0078. 子集

### 题目地址(78. 子集)

<https://leetcode-cn.com/problems/subsets/>

### 题目描述

```
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

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

示例:

输入: nums = [1,2,3]
输出:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

```

### 前置知识

* [回溯](/leetcode-solution/thinkings/backtrack.md)

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 思路

回溯的基本思路清参考上方的回溯专题。

子集类题目和全排列题目不一样的点在于其需要在递归树的所有节点执行**加入结果集** 这一操作，而不像全排列需要在叶子节点执行**加入结果集**。

### 关键点解析

* 回溯法
* backtrack 解题公式

### 代码

* 语言支持：JS，C++，Java，Python

JavaScript Code:

```js
function backtrack(list, tempList, nums, start) {
  list.push([...tempList]);
  for (let i = start; i < nums.length; i++) {
    tempList.push(nums[i]);
    backtrack(list, tempList, nums, i + 1);
    tempList.pop();
  }
}
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function (nums) {
  const list = [];
  backtrack(list, [], nums, 0);
  return list;
};
```

C++ Code：

```
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        auto ret = vector<vector<int>>();
        auto tmp = vector<int>();
        backtrack(ret, tmp, nums, 0);
        return ret;
    }

    void backtrack(vector<vector<int>>& list, vector<int>& tempList, vector<int>& nums, int start) {
        list.push_back(tempList);
        for (auto i = start; i < nums.size(); ++i) {
            tempList.push_back(nums[i]);
            backtrack(list, tempList, nums, i + 1);
            tempList.pop_back();
        }
    }
};
```

Java Code：

```java
class Solution {
    // 结果
    List<List<Integer>> res = new ArrayList();
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(nums, 0, new ArrayList<Integer>());
        return res;
    }

    public void backtrack(int[] nums, int start, ArrayList<Integer> track)
    {
        // 注意：深拷贝
        res.add(new ArrayList(track));
        for(int i=start; i<nums.length;i++)
        {
            // 做选择
            track.add(nums[i]);
            // 回溯
            backtrack(nums, i+1, track);
            // 撤销选择
            track.remove(track.size()-1);
        }
    }
}
```

python Code：

```py
class Solution:
    def subsets(self, nums):
        self.res = []
        self.track = []
        self.backtrack(nums, 0, self.track)

        return self.res

    def backtrack(self, nums, start, track):
        # 注意深拷贝
        self.res.append(list(self.track))
        for i in range(start, len(nums)):
            # 做选择
            self.track.append(nums[i])
            # 回溯
            self.backtrack(nums, i+1, self.track)
            # 撤销选择
            self.track.pop()
```

### 相关题目

* [39.combination-sum](/leetcode-solution/medium/39.combination-sum.md)
* [40.combination-sum-ii](/leetcode-solution/medium/40.combination-sum-ii.md)
* [46.permutations](/leetcode-solution/medium/46.permutations.md)
* [47.permutations-ii](/leetcode-solution/medium/47.permutations-ii.md)
* [90.subsets-ii](/leetcode-solution/medium/90.subsets-ii.md)
* [113.path-sum-ii](/leetcode-solution/medium/113.path-sum-ii.md)
* [131.palindrome-partitioning](/leetcode-solution/medium/131.palindrome-partitioning.md)

大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。 大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 ![](https://p.ipic.vip/tv8mab.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/78.subsets.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.