集合的子集

[编程题]集合的子集

热度指数：11204 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知数组A和其大小n，请返回A的所有非空子集。要求A中元素个数不大于20且互异。各子集内部从大到小排序,子集间字典逆序排序。

测试样例：

[123,456,789]

返回：{[789,456,123],[789,456],[789,123],[789],[456 123],[456],[123]}

算法知识视频讲解

Python

你回家了我在等你呢

# -*- coding:utf-8 -*-
class Subset:
def __init__(self):
self.res = []
self.Li = []

# 返回二维[[],[],[]]
def subgetSubsets(self, A, ind):
n = len(A)
#print(ind,n)
if ind >= n:
if self.Li!=[]:
self.res.append(self.Li[::1])
print(self.res)
return
#print(ind)
self.Li.append(A[ind])
self.subgetSubsets(A, ind + 1)
self.Li.pop()
self.subgetSubsets(A, ind + 1)
return

def getSubsets(self, A, n):
# write code here
A.sort(reverse=True)
self.subgetSubsets(A, 0)
return self.res

发表于 2019-05-30 09:56:35 回复(0)

Python

华科平凡

python dfs solution

# -*- coding:utf-8 -*-
class Subset:
    # 返回二维[[],[],[]]
    def getSubsets(self, A, n):
        # write code here
        res = []
        A.sort()
        self.dfs(A, res, [])
        return sorted(res, key=lambda c: "".join(map(str, c)), reverse=True)

    def dfs(self, arr, res, path):
        if path != sorted(path, reverse=True):
            return
        if path:
            res.append(path)
        if not arr:
            return
        for i in arr:
            a = arr[:]
            a.remove(i)
            self.dfs(a, res, path + [i])

编辑于 2017-10-31 18:12:23 回复(0)

Python

Yannyezixin

思路：

初始结果集为 [ [A[0] ]

遍历剩余 A[1] ~ A[n - 1]. 每取出一个元素遍加到结果集：

复制一份结果集，并把元素加入到结果集中的每个集合的头部
合并复制的结果集 + 只有当前元素的集合 + 原始结果集

# -*- coding:utf-8 -*-
class Subset:
    # 返回二维[[],[],[]]
    def getSubsets(self, A, n):
        result = [[A[0]]]
        for i in range(1, n):
            tmp = result[:]
            for j in range(len(tmp)):
                tmp[j] = [A[i]] + tmp[j]
            result = tmp + [[A[i]]] + result
        return result

发表于 2016-08-05 10:17:04 回复(1)