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

Problem

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

Example:

1
2
3
4
5
6
7
8
9
10
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
permute(0, nums, result);
return result;
}

private void permute(int d, int[] nums, List<List<Integer>> result) {
// base case
if (d == nums.length) {
List<Integer> list = new ArrayList<>();
for (int val : nums) list.add(val);
result.add(list);
return;
}

for (int i = d; i < nums.length; ++i) {
swap(nums, d, i);
permute(d + 1, nums, result);
swap(nums, d, i);
}
}

private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}

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
2
3
4
5
6
7
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

Simple Modification

Use a set to remove duplicate elements.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private void permuteUnique(int d, int[] nums, List<List<Integer>> result) {
// base case
if (d >= nums.length - 1) {
List<Integer> list = new ArrayList();
for (int val : nums) list.add(val);
result.add(list);
return;
}

// set
Set<Integer> set = new HashSet<>();

for (int i = d; i < nums.length; ++i) {
if (set.contains(nums[i]) == false) {
set.add(nums[i]); // add to set
swap(nums, d, i);
permuteUnique(d + 1, nums, result);
swap(nums, d, i);
}
}
}

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


Comment