集合的所有子集(一)

问题简述

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

集合的所有子集(一)_牛客题霸_牛客网

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

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