Problem

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. OR Given a collection of numbers, return all possible permutations.

Examples

Example 1:

nums = [1,2,3]

Output: [
	[1,2,3]
	[1,3,2]
	[2,1,3]
	[2,3,1]
	[3,1,2]
	[3,2,1]
]

NOTE: No two entries in the permutation sequence should be the same. For the purpose of this problem, assume that all the numbers in the collection are unique.

Warning : DO NOT USE LIBRARY FUNCTION FOR GENERATING PERMUTATIONS. Example : next_permutations in C++ / itertools.permutations in python. If you do, we will disqualify your submission retroactively and give you penalty points.

Follow up problem - Permutations II

Solution

Method 1 - Backtracking storing current permutation in List

Code

Java
Code with list only
public List<List<Integer>> permute(int[] nums) {
   List<List<Integer>> list = new ArrayList<>();
   backtrack(list, new ArrayList<>(), nums);
   return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> subAns, int [] nums){
   if(tempList.size() == nums.length){
      list.add(new ArrayList<>(subAns));
   } else{
      for(int i = 0; i < nums.length; i++){ 
         if(subAns.contains(nums[i])) {
	         continue; // element already exists, skip
		    }
         tempList.add(nums[i]);
         backtrack(list, tempList, nums);
         tempList.remove(tempList.size() - 1);
      }
   }
}

Method 2 - Using HashSet

Code

Java
public List<List<Integer>> permute(int[] nums) {
	List<List<Integer>> ans = new ArrayList<>();
	backtrack(ans, new ArrayList<>(), new HashSet<>(), nums);
	return ret;
}

private void backtrack(List<List<Integer>> ans, List<Integer> subAns, Set<Integer> tmpSet, int[] nums) {
	if (tmpSet.size() == nums.length) {
		ans.add(new ArrayList<>(new ArrayList<>(tmpList)));
		return;
	}

	for (int i = 0; i < nums.length; i++) {
		if (tmpSet.contains(nums[i])) {
			continue;
		}
		
		tmpSet.add(nums[i]);
		subAns.add(nums[i]);
		
		backtrack(ret, subAns, tmpSet, nums);
		
		tmpSet.remove(subAns.get(tmpList.size()-1));
		subAns.remove(subAns.size()-1);
	}
}

Note we are using tmpSet to complment subAns list, as we need contains operations, which is O(1) for hashset, but O(n) for list.

Approach 2 - Backtracking with Visited Array

A list to represent permutation constructed so far, path A list to record which letters are already used, used, visited[i] == true means ith letter in the origin list has been used.

public List<List<Integer>> permute(int[] nums) {
	boolean[] visited = new boolean[nums.length];
	List<List<Integer>> ans = new ArrayList<>();
	helper(nums,visited,ans, new ArrayList<>());
	return ans;
}

void helper(int[] nums, boolean[] visited, List<List<Integer>> ans, List<Integer> subAns) {
	if (subAns.size() == nums.length){
		ans.add(new ArrayList<>(subAns));
		return;
	}
	for(int i=0;i<nums.length;i++){
		if(visited[i]) {
			continue;
		}
		
		subAns.add(nums[i]);
		visited[i]=true;

		helper(nums,visited,ans,subAns);

		visited[i]=false;
		subAns.remove(subAns.size()-1);
	}
}

Note: It is very important to do:

ans.add(new ArrayList<>(subAns));

and not:

ans.add(subAns);

As, subAns is constantly modified. So, they will be become empty[] eventually, so we will get wrong answer. new ArrayList<>(subAns) creates deep copy.

Method 2 - Backtracking with Swapping Elements in Array

We can follow following steps: Step 0: Initialize the variables start and end with start = 0 and end = n - 1. Call the method: permutations(array, start, end).

Step 1: Loop over the array from start to end using an index. Step 2: Fix the character at the current index by swapping the character at start with the character at the index. Step 3: Recursively generate all permutations for the remaining positions by calling the method again with updated parameters: permutations(array, start + 1, end). Step 4: Backtrack by swapping the character at start back with the character at the index.

Try to dry run with n = 3 and nums = [1,2,3]

Code

Java
private void permutation(int[] nums, int start, int end, List<List<Integer> ans) {
	if (start == end) {
		ans.add(Arrays.stream(nums)
                             .boxed()
                             .collect(Collectors.toList()););
	}
	for (int i=start; i<= end; i++){
		swap(nums, start, i);
		permutation(nums, start+1, end);
		swap(nums, start, i);
	}
}

private int[] swap(int[] a, int i, int j) {
	char temp = a[i];
	a[i] = a[j];
	a[j] = temp;
	return a;
}

Complexity

The complexity of all solutions is:

  • ⏰ Time complexity: O(n*n!) where n is number of elements in array
  • 🧺 Space complexity: O(n!)

Why?