# 集合的所有子集(一)

![last modify](https://img.shields.io/static/v1?label=last%20modify\&message=2022-10-14%2014%3A59%3A33\&color=yellowgreen\&style=flat-square) [![](https://img.shields.io/static/v1?label=\&message=%E4%B8%AD%E7%AD%89\&color=yellow\&style=flat-square)](../../../..#中等) [![](https://img.shields.io/static/v1?label=\&message=%E7%89%9B%E5%AE%A2\&color=green\&style=flat-square)](../../../..#牛客) [![](https://img.shields.io/static/v1?label=\&message=%E9%80%92%E5%BD%92\&color=blue\&style=flat-square)](../../../..#递归)

**问题简述**

```
现在有一个没有重复元素的整数集合S，求S的所有子集
注意：
    你给出的子集中的元素必须按升序排列
    给出的解集中不能出现重复的元素
```

> [集合的所有子集(一)\_牛客题霸\_牛客网](https://www.nowcoder.com/practice/c333d551eb6243e0b4d92e37a06fbfc9)

**思路：递归+回溯（01背包）**

<details>

<summary><strong>Python</strong></summary>

```python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param S int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def subsets(self , S: List[int]) -> List[List[int]]:
        # write code here
        
        N = len(S)
        ret = []
        tmp = []
        
        def dfs(i):
            if i == N:
                ret.append(tmp[:])
                return
            
            # 不要当前元素
            dfs(i + 1)
            
            # 要当前元素
            tmp.append(S[i])
            dfs(i + 1)
            tmp.pop()
        
        dfs(0)
        return ret
```

</details>
