上周一道算法题（五十九）

终于把缺的补回来了，呼呼。。。

题目：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。eg：输入: nums = [1,2,3]输出:[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]

思路：做了上一道题(建议先看上一道题)，这道题已经是easy级别的了。以例题来说，[1，2，3]就相当于上一道题目的n，然后需要你求的结果就是k=0，k=1，k=2，k=3的集合，把上一道题目的答案改一下，加个参数即可，详细的看代码：

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 自定义的dfs，只是多了一个参数nums
        def dfs(begin, end, k, temp, result, nums):
            if k: #如果k不等于0就遍历，遍历的范围是begin至end
                for i in range(begin,end):
                    if (end - i + 1 < k): break #剪枝
                    temp.append(nums[i-1])#注意这里添加的不再是i
                    dfs(i + 1, end, k - 1, temp, result, nums)
                    del temp[-1]
            else:#k=0时记录
                one = []
                for i in temp:
                    one.append(i)
                result.append(one)#将深拷贝的结果记录下来
        # 定义结果，默认加上[]，即k=0的情况
        result = [[]]
        # 自己造个k
        k = len(nums)
        # k=1，k=2。。k=len(nums)的情况都调用一下即可
        while k:
            #调用方法，参数分别是：遍历的起点/终点/k/单个数组/数组集合
            dfs(1, len(nums)+1, k, [], result, nums)
            k -= 1
        return result

效率还行。

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!