Reference: Permutations I & Permutations II EPI 15.4

Difficulty: Medium

## Problem

Given a collection of

`distinct`

integers, return all possible permutations.

**Example:**

1 | Input: [1,2,3] |

**Follow up:** Consider the case when there are duplicates, but we donâ€™t allow duplicate list in the result.

## Analysis

### Backtracking

First consider the example `[1, 2, 3]`

. When `d = 0`

, we are in depth 0, which means the first level where we consider the first element in the list. Thus, we loop over 1, 2, and 3.

- For 1, we do the permutation subproblem
`[2, 3]`

. - For 2, we do the permutation subproblem
`[1, 3]`

. - For 3, we do the permutation subproblem
`[1, 2]`

.

**The question is:** How could we do the subproblem in an elegant way? E.g., when `d`

equals 2 and 3. We can use `swapping`

.

Take 2 as an example. When we pick 2, we swap 2 with the first element and make the array `[2, 1, 3]`

and set `d`

as 1 pointing to the first element of our subproblem `[1, 3]`

.

So when `d`

equals to the length of `nums`

, the last element will be chosen, which means now the elements in the array is a result we can put into the result list.

**Note:**

- In the base case when adding a new list, we should add it one by one. If
`nums`

is declared as a`List`

, we can write code like`result.add(new ArrayList<>(nums))`

to make copy of a list. - If
`nums`

is declared as a`List`

, we can use`Collections.swap(nums, d, i)`

.

1 | public List<List<Integer>> permute(int[] nums) { |

**Time:** $O(N \times N!)$. Initially we have $N$ choices, and in each choice we have $(N - 1)$ choices, and so on. Notice that at the end when adding the list to the result list, it takes $O(N)$.**Space:** $O(N \times N!)$. The call stack takes $N$, but there are $N!$ solutions and each of them requires $N$ space.

## Follow-Up

Given a collection of numbers that `might contain duplicates`

, return all possible `unique`

permutations.

1 | Input: [1,1,2] |

### Simple Modification

Use a `set`

to remove duplicate elements.

1 | private void permuteUnique(int d, int[] nums, List<List<Integer>> result) { |

**Time:** $O(N \times N!)$ since set operations take constant time.**Space:** $O(N \times N!)$