leetcode78. 子集

题目：

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

思路：回溯。

改变一下回溯函数的结束条件即可。
如图，每一个红圈都表示一个子集，而且红圈中的元素都是回溯函数的开始数组。

代码：

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        l = len(nums)

        def backtrack(start, array):
            res.append(list(array))
            if start == l:
                return

            for i in range(start, l):
                array.append(nums[i])
                backtrack(i+1, array)
                array.pop()

        backtrack(0, [])
        return res