# 47. Permutations I & II

Reference: Permutations I & Permutations II EPI 15.4
Difficulty: Medium

## Problem

Given a collection of distinct integers, return all possible permutations.

Example:

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).

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.

### Simple Modification

Use a set to remove duplicate elements.

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

Comment Junhao Wang
a software engineering cat