注意:
你给出的子集中的元素必须按升序排列
给出的解集中不能出现重复的元素
数据范围:,集合中的任意元素满足
要求:空间复杂度 ,时间复杂度
# # # @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
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。还有一个需要注意的点是要把每次第一个选择的剔除出去,才能进行循环的下一个数字的选择。