集合的所有子集(一)

[编程题]集合的所有子集(一)

热度指数：40562 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

给出的解集中不能出现重复的元素

数据范围： $1 \le n \le 5$ ，集合中的任意元素满足 $|val| \le 10$

要求：空间复杂度 $O(n!)$ ，时间复杂度 $O(n!)$

示例1

输入

[1,2,3]

输出

[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

示例2

输入

[]

输出

[]

算法知识视频讲解

Python

奋斗的习习张

#
# 
# @param A int整型一维数组 
# @return int整型二维数组
# 非递归方法比较好理解
class Solution:
    def subsets(self , A ):
        # write code here
        A.sort()
        res = [A[::]]
        temp = [A]
        while len(temp) > 0:
            temp_len = len(temp)
            for index in range(temp_len):    # [1, 2, 3]
                array = temp.pop(0)
                length = len(array)  # 3
                for i in range(length):  # 0, 1, 2
                    num = array.pop(0)   # array = [2, 3]
                    sort_arr = array[::]
                    sort_arr.sort()
                    if sort_arr not in res:
                        res = [sort_arr] + res  # res = [[1, 2, 3], [2, 3]]
                    temp.append(array[::])
                    array.append(num)  # array = [2, 3, 1]
        return res

发表于 2021-08-02 23:08:14 回复(0)

Python

LHC0512

Python

import itertools

class Solution:
    def subsets(self, A):
        res = []
        res.append([])
        for i in range(1, len(A) + 1):
            s = itertools.combinations(A, i)
            for v in s:
                res.append(list(v))
        return res

发表于 2021-02-23 21:28:01 回复(0)

Python

小狗最6

class Solution:
def subsets(self , A ):
# write code here
res = []
state = []
def back(state,num = 0):
if state in res:
return
else:
res.append(state)
for i in range(num,len(A)):
back(state + [A[i]],i+1)
A.sort()
back(state,0)
return res

发表于 2020-08-30 18:19:19 回复(0)

Python

黄沙遮天

class Solution:
    def subsets(self, A):
    # write code here
        A.sort()
        res=[]
        def dfs(m,n,k,temp,A):
            if k==0:
                w=[]
                for i in temp:
                    w.append(i)
                res.append(w)
                return
            for i in range(m,n+1):
                temp.append(A[i])
                dfs(i+1,n,k-1,temp,A)
                temp.pop()
        for i in range(len(A)+1):
            dfs(0,len(A)-1,i,[],A)
        return res

通过不同的k，来查找含有不同元素个数的非递减子集。当k设定为某一值时，我们通过遍历的方法每次选择一个值，k值就减1，直到k=0，此时的子集中的元素个数就是k。还有一个需要注意的点是要把每次第一个选择的剔除出去，才能进行循环的下一个数字的选择。

发表于 2020-08-19 20:46:09 回复(0)