---
# System prepended metadata

title: 78. Subsets
tags: [Leetcode, medium, python, backtracking, Top 100 Liked Questions]

---

###### 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)
``` python=
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] 
```

``` python=
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)
```