# Permutations

medium

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

Example:

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

Output:

[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
``````

## Solution

Backtracking - Add Remove (6ms 34.59%）

``````class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
if (nums == null || nums.length == 0) {
return ans;
}
boolean[] visited = new boolean[nums.length];

// Totla number of permutations: n! = n * (n - 1) * ... 3 * 2 * 1
permuteHelper(nums, visited, new LinkedList<>(), ans);
return ans;
}

private void permuteHelper(int[] nums, boolean[] visited, List<Integer> list, List<List<Integer>> ans) {
// When a permutation reaches the desired length, add a COPY to ans
if (list.size() == nums.length) {
return;
}
for (int i = 0; i < nums.length; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
permuteHelper(nums, visited, list, ans);
list.remove(list.size() - 1);
visited[i] = false;
}
}
}
``````

Backtracking - Swap - LeetCode Official (4ms 90.37%)

``````class Solution {
public void backtrack(int n,
ArrayList<Integer> nums,
List<List<Integer>> output,
int first) {
// if all integers are used up
if (first == n)
for (int i = first; i < n; i++) {
// place i-th integer first
// in the current permutation
Collections.swap(nums, first, i);
// use next integers to complete the permutations
backtrack(n, nums, output, first + 1);
// backtrack
Collections.swap(nums, first, i);
}
}

public List<List<Integer>> permute(int[] nums) {
// init output list
List<List<Integer>> output = new LinkedList();

// convert nums into list since the output is a list of lists
ArrayList<Integer> nums_lst = new ArrayList<Integer>();
for (int num : nums)

int n = nums.length;
backtrack(n, nums_lst, output, 0);
return output;
}
}
``````

Time complexity : `O(N!)` to build N! solutions.

Space complexity : `O(N!)` since one has to keep N! solutions.