讨论/《深度优先搜索》 - 练习:子集 II/
《深度优先搜索》 - 练习:子集 II
共 3 个回复
class Solution:
    def subsetsWithDup(self, ns: List[int]) -> List[List[int]]:
        ns.sort()
        res = []
        vstd = [0 for i in range(len(ns))]
        def dfs(pth, idx):
            if idx == len(ns):
                res.append(pth)
                return
            if not idx or ns[idx] != ns[idx-1] or vstd[idx-1]:
                vstd[idx] = 1
                dfs(pth + [ns[idx]], idx + 1)
                vstd[idx] = 0
            dfs(pth, idx+1)
        dfs([], 0)
        return res
class Solution:
    def subsetsWithDup(self, ns: List[int]) -> List[List[int]]:
        res = []
        ns.sort()
        def dfs(idx, pth):
            res.append(pth)
            for i in range(idx, len(ns)):
                if i == idx or ns[i] != ns[i-1]:
                    dfs(i+1, pth + [ns[i]])
        dfs(0, [])
        return res
class Solution:
    def subsetsWithDup(self, ns: List[int]) -> List[List[int]]:
        ns.sort()
        s = set()
        def dfs(pth,idx):
            if idx == len(ns):
                s.add(tuple(pth))
                return
            dfs(pth + [ns[idx]],idx+1)
            dfs(pth,idx+1)
        dfs([],0)
        return list(map(lambda x:list(x),s))