# 2022-06-05

## [78. Subsets](https://leetcode.com/problems/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

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

```go
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](https://leetcode.com/problems/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

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

```go
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
}
```