###### tags: `Leetcode` `medium` `backtracking` `python` `Top 100 Liked Questions`

# 78. Subsets

## [題目連結:] https://leetcode.com/problems/subsets/

## 題目:
Given an integer array ```nums``` of **unique** elements, return all possible subsets (the power set).

The solution set ```must not``` contain duplicate subsets. Return the solution in ```any order```.

**Example 1:**

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

**Example 2:**

Input: nums = [0]
Output: [[],[0]]

## 解題想法:
兄弟題目: [90. Subsets II](/oBRbDRUpRyGciCV4VzZl-g)
* 求數組元素的power set組合
* 每個元素都不同，數字不會重複
* 遞歸求解:dfs傳遞參數
* nums:數組
* cur_pos:當前數組使用位置
* path:當前list
* 加入res順序如下

nums=[1,2,3]
[]
[1]
[1 2]
[1 2 3]
[1 3]
[2]
[2 3]
[3]

## Python: (Sol1)

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.res=[]
        self.dfs(nums,0,[])
        return self.res
    def dfs(self,nums,cur_pos,path):
        self.res.append(path)
        for i in range(cur_pos,len(nums)):
            self.dfs(nums,i+1,path+[nums[i]])

result = Solution()
nums = [1,2,3]
ans = result.subsets(nums)
print(ans)

## Python: Sol2
* 迭代
想法:每個值依序與前面所有相加

    []
1:  [1]
2:  [2],[1,2]
3:  [3],[1,3],[2,3],[1,2,3] 

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        ans = [[]]
        for cur_val in nums:
            ans += [[cur_val]+item for item in ans]
        return ans
result = Solution()
nums = [1,2,3]
ans = result.subsets(nums)
print(ans)