# 2022-06-06

## [47. Permutations II](https://leetcode.com/problems/permutations-ii/)

### Description

Given a collection of numbers, `nums`, that might contain duplicates, return *all possible unique permutations **in any order**.*

**Example 1:**

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

**Example 2:**

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

**Constraints:**

* `1 <= nums.length <= 8`
* `-10 <= nums[i] <= 10`

### Solution

#### Approach #0

```go
func permuteUnique(nums []int) (ans [][]int) {
    sort.Ints(nums)
    n := len(nums)
    vis := make([]bool, len(nums))
    var tmp []int
    var backtrack func(int)
    backtrack = func(cur int) {
        if cur == n {
            ans = append(ans, append([]int(nil), tmp...))
            return
        }
        for i, num := range nums {
            if vis[i] || i > 0 && !vis[i-1] && nums[i-1] == num {
                continue
            }
            vis[i] = true
            tmp = append(tmp, num)
            backtrack(cur + 1)
            tmp = tmp[:len(tmp)-1]
            vis[i] = false
        }
    }
    backtrack(0)
    return
}
```

## [39. Combination Sum](https://leetcode.com/problems/combination-sum/)

### Description

Given an array of **distinct** integers `candidates` and a target integer `target`, return *a list of all **unique combinations** of* `candidates` *where the chosen numbers sum to* `target`*.* You may return the combinations in **any order**.

The **same** number may be chosen from `candidates` an **unlimited number of times**. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is **guaranteed** that the number of unique combinations that sum up to `target` is less than `150` combinations for the given input.

**Example 1:**

```
Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
```

**Example 2:**

```
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
```

**Example 3:**

```
Input: candidates = [2], target = 1
Output: []
```

**Constraints:**

* `1 <= candidates.length <= 30`
* `1 <= candidates[i] <= 200`
* All elements of `candidates` are **distinct**.
* `1 <= target <= 500`

### Solution

#### Approach #0

```go
func combinationSum(candidates []int, target int) (ans [][]int) {
    sort.Ints(candidates)
    n := len(candidates)
    var t []int
    var backtrack func(cur, index int)
    backtrack = func(cur, index int) {
        if cur == target {
            ans = append(ans, append([]int(nil), t...))
            return
        }
        if cur > target {
            return
        }
        for i := index; i < n; i++ {
            t = append(t, candidates[i])
            backtrack(cur+candidates[i], i)
            t = t[:len(t)-1]
        }
    }
    backtrack(0, 0)
    return
}
```

## [40. Combination Sum II](https://leetcode.com/problems/combination-sum-ii/)

### Description

Given a collection of candidate numbers (`candidates`) and a target number (`target`), find all unique combinations in `candidates` where the candidate numbers sum to `target`.

Each number in `candidates` may only be used **once** in the combination.

**Note:** The solution set must not contain duplicate combinations.

**Example 1:**

```
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
```

**Example 2:**

```
Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]
```

**Constraints:**

* `1 <= candidates.length <= 100`
* `1 <= candidates[i] <= 50`
* `1 <= target <= 30`

### Solution

#### Approach #0

```go
func combinationSum2(candidates []int, target int) (ans [][]int) {
    sort.Ints(candidates)
    n := len(candidates)
    vis := make([]bool, n)
    var t []int
    var backtrack func(index, cur int)
    backtrack = func(index, cur int) {
        if cur == target {
            ans = append(ans, append([]int(nil), t...))
            return
        }
        if cur > target {
            return
        }
        for i := index; i < n; i++ {
            if i > 0 && !vis[i-1] && candidates[i-1] == candidates[i] {
                continue
            }
            t = append(t, candidates[i])
            vis[i] = true
            backtrack(i+1, cur+candidates[i])
            vis[i] = false
            t = t[:len(t)-1]
        }
    }
    backtrack(0, 0)
    return
}
```