集合的所有子集(二)

# -*- coding: utf-8 -*-

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型二维数组
#
class Solution:
    """
    题目：
        集合的所有子集(二)
        https://www.nowcoder.com/practice/a3dfd4bc8ae74fad9bc65d5ced7ae813?tpId=117&&tqId=39446&rp=1&ru=/ta/job-code-high&qru=/ta/job-code-high/question-ranking
    参考：
        大神：代码界的小白
        https://leetcode.cn/problems/sliding-window-median/solution/hua-dong-chuang-kou-zhong-wei-shu-by-lee-7ai6/
    算法：
        题目要求：寻找nums的所有子集，结果按字典序排序
        1. 对nums进行排序
        2. 定义回溯函数dfs(combine, idx)，初始combine为[]，idx为0。
            a. 记录子集combine
            b. 枚举可选元素，加入combine，从下一个下标继续搜索；搜索完毕，回溯
    复杂度：
        时间复杂度：O(nlogn + n * 2^n) = O(n * 2^n)，排序算法的复杂度：O(nlogn)，构造子集：共2^n种状态，每种状态需要O(n)复杂度构造子集，构造子集的总复杂度为O(n * 2^n)
        空间复杂度：O(n)，临时数组combine
    """

    def subsets(self, nums):
        # write code here
        def dfs(combine, idx):
            res.append(combine[:])
            for i in range(idx, n):
                if i > idx and nums[i] == nums[i - 1]: # 剪枝：前一个相同的数已经回溯了
                    continue
                combine.append(nums[i])
                dfs(combine, i + 1)
                combine.pop()

        nums.sort()
        res, n = [], len(nums)

        dfs([], 0)

        return res


if __name__ == '__main__':
    s = Solution()

    # nums = [1, 2]

    # nums = [1]

    nums = [1, 1, 1]

    # nums = [3, 6, 7, 5]

    res = s.subsets(nums)

    print res