# 2022-06-05

## 78. Subsets

### Description

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]]``````

Constraints:

• `1 <= nums.length <= 10`

• `-10 <= nums[i] <= 10`

• All the numbers of `nums` are unique.

### Solution

#### Approach #0

``````func subsets(nums []int) (ans [][]int) {
n := len(nums)
for p := 0; p < 1<<n; p++ {
var a []int
for i, num := range nums {
if p>>i&1 > 0 {
a = append(a, num)
}
}
ans = append(ans, a)
}
return
}``````

#### Approach #1

``````func subsets(nums []int) (ans [][]int) {
n := len(nums)
var tmp []int
var dfs func(int)
dfs = func(cur int) {
if cur == n {
ans = append(ans, append([]int(nil), tmp...))
return
}
tmp = append(tmp, nums[cur])
dfs(cur + 1)
tmp = tmp[:len(tmp)-1]
dfs(cur + 1)
}
dfs(0)
return
}``````

## 90. Subsets II

### Description

Given an integer array `nums` that may contain duplicates, 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,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]``````

Example 2:

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

Constraints:

• `1 <= nums.length <= 10`

• `-10 <= nums[i] <= 10`

### Solution

#### Approach #0

``````func subsetsWithDup(nums []int) (ans [][]int) {
sort.Ints(nums)
n := len(nums)
outer:
for p := 0; p < 1<<n; p++ {
var a []int
for i, num := range nums {

if p>>i&1 > 0 {
if i > 0 && p>>(i-1)&1 == 0 && nums[i-1] == num {
continue outer
}
a = append(a, num)
}

}
ans = append(ans, append([]int(nil), a...))
}
return
}``````

#### Approach #1

``````func subsetsWithDup(nums []int) (ans [][]int) {
sort.Ints(nums)
n := len(nums)
var tmp []int
var dfs func(bool, int)
dfs = func(choosePre bool, cur int) {
if cur == n {
ans = append(ans, append([]int(nil), tmp...))
return
}
dfs(false, cur+1)
if !choosePre && cur > 0 && nums[cur-1] == nums[cur] {
return
}
tmp = append(tmp, nums[cur])
dfs(true, cur+1)
tmp = tmp[:len(tmp)-1]
}
dfs(false, 0)
return
}``````

Last updated