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!)$