# Question

Formatted question description: https://leetcode.ca/all/46.html

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

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]


Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]


Example 3:

Input: nums = [1]
Output: [[1]]


Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

# Algorithm

When n=1, there is only one number a1 in the array, and there is only one total permutation, which is a1

When n=2, there is a1a2 in the array at this time, and there are two kinds of full arrays, a1a2 and a2a1. Then, considering the relationship with the above situation at this time, you can find that it is actually added in the two positions before and after a1. A2

When n=3, there are a1a2a3 in the array. At this time, there are six kinds of full arrays, namely a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, and a3a2a1. Then according to the above conclusion, it is actually obtained by adding a3 at different positions on the basis of a1a2 and a2a1.

_ a1 _ a2 _: a3a1a2, a1a3a2, a1a2a3

_ a2 _ a1 _: a3a2a1, a2a3a1, a2a1a3

# Code

• import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

public class Permutations {

public static void main(String[] args) {
Permutations out = new Permutations();
Solution_iteration s = out.new Solution_iteration();

System.out.println(s.permute(new int[]{1, 2, 3}));
}

// time: O(N)
// space: O(N)
public class Solution_iteration {
public List<List<Integer>> permute(int[] nums) {

List<List<Integer>> list = new ArrayList<>();

if (nums == null || nums.length == 0) {
return list;
}

list.add(new ArrayList<Integer>()); // add empty single list, to make below loop going

for (int i = 0; i < nums.length; i++) {
List<List<Integer>> tmpList = new ArrayList<>();

int insertNum = nums[i];

// get each permutations. eg, [1,2], [2,1]
for (List<Integer> singlePerm: list) {

// eg. [1,2] and insert 3, there are 3 insert position
int singleListSize = singlePerm.size();
for (int index = 0; index <= singleListSize; index++) { // @note: the usage of arraylist add() api: add(atIndex, value)

// @note: don't forget roll back
singlePerm.remove(index);
}
}

// update list. @note: possible issue, this is not deep copy
list = tmpList;
}

return list;
}
}

// time: O(N)
// space: O(N)
class Solution_dfs {

List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> permute(int[] nums) {

if (nums == null || nums.length == 0) {
return result;
}

dfs(nums, new HashSet<Integer>(), new ArrayList<Integer>()); // hashset 或者是boolean[]

return result;
}

private void dfs(int[] nums, HashSet<Integer> isVisited, ArrayList<Integer> onePath) {

if (isVisited.size() == nums.length) {
return;
}

for (int i = 0; i < nums.length; i++) {
if (!isVisited.contains(i)) {

dfs(nums, isVisited, onePath);

isVisited.remove(i);
onePath.remove(onePath.size() - 1);
}
}
}
}

}

############

class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private boolean[] vis;
private int[] nums;

public List<List<Integer>> permute(int[] nums) {
this.nums = nums;
vis = new boolean[nums.length];
dfs(0);
return ans;
}

private void dfs(int i) {
if (i == nums.length) {
return;
}
for (int j = 0; j < nums.length; ++j) {
if (!vis[j]) {
vis[j] = true;
dfs(i + 1);
t.remove(t.size() - 1);
vis[j] = false;
}
}
}
}

• // OJ: https://leetcode.com/problems/permutations/
// Time: O(N!)
// Space: O(N)
class Solution {
vector<vector<int>> ans;
void dfs(vector<int> &nums, int start) {
if (start == nums.size() - 1) {
ans.push_back(nums);
return;
}
for (int i = start; i < nums.size(); ++i) {
swap(nums[i], nums[start]);
dfs(nums, start + 1);
swap(nums[i], nums[start]);
}
}
public:
vector<vector<int>> permute(vector<int>& nums) {
dfs(nums, 0);
return ans;
}
};

• '''
remove an element by its value from a set

>>> my_set = {1, 2, 3, 4, 5}
>>> my_set.remove(3)
>>> print(my_set)
{1, 2, 4, 5}

------

cannot remove an element by index from a set in Python3
need to convert the set to a list

>>> my_set = {1, 2, 3, 4, 5}
>>> my_list = list(my_set)
>>> del my_list[2] # remove the element at index 2
>>> my_set = set(my_list)
>>> print(my_set)
{1, 2, 4, 5}
'''

class Solution: # iterative
def permute(self, nums: List[int]) -> List[List[int]]:
res = [[]]

if nums is None or len(nums) == 0:
return ans

for num in nums:
new_res = []
for perm in res:
for i in range(len(perm) + 1):
new_perm = perm[:i] + [num] + perm[i:]
new_res.append(new_perm)

res = new_res

return res

class Solution: # iterative, single_perm.insert(index, num)
def permute(self, nums: List[int]) -> List[List[int]]:
ans = [[]]

if nums is None or len(nums) == 0:
return ans

for num in nums:
tmp_list = []

for single_perm in ans:
for index in range(len(single_perm) + 1):
single_perm.insert(index, num)
tmp_list.append(single_perm.copy())
single_perm.pop(index)

ans = tmp_list

return ans

'''
In Python 3, both the discard() and remove() methods of a set object are used to remove an element from the set, but there is one key difference:

* discard() removes the specified element from the set if it is present, but does nothing if the element is not present.
* remove() removes the specified element from the set if it is present, but raises a KeyError exception if the element is not present.

>>> a
{33, 66, 11, 44, 22, 55}
>>> a
{33, 66, 11, 44, 55}

>>>
>>> a.remove(200)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
KeyError: 200
'''

'''
>>> v1 = set([])
>>> v2 = set()
>>>
>>> v1
set()
>>> v2
set()
'''
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res = []
visited = set([])

def dfs(nums, path, res, visited):
if len(path) == len(nums):
res.append(path + [])
return

for i in range(0, len(nums)):
if i not in visited:
path.append(nums[i])
dfs(nums, path, res, visited)
path.pop()
visited.discard(i) # remove(i) will throw exception if i not existing

dfs(nums, [], res, visited)
return res

############

class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def dfs(i):
if i == n:
ans.append(t[:])
return
for j in range(n):
if not vis[j]:
vis[j] = True
t[i] = nums[j]
dfs(i + 1)
vis[j] = False

n = len(nums)
vis = [False] * n
t = [0] * n
ans = []
dfs(0)
return ans


• func permute(nums []int) (ans [][]int) {
n := len(nums)
t := make([]int, n)
vis := make([]bool, n)
var dfs func(int)
dfs = func(i int) {
if i == n {
cp := make([]int, n)
copy(cp, t)
ans = append(ans, cp)
return
}
for j, v := range nums {
if !vis[j] {
vis[j] = true
t[i] = v
dfs(i + 1)
vis[j] = false
}
}
}
dfs(0)
return
}

• function permute(nums: number[]): number[][] {
const n = nums.length;
const res: number[][] = [];
const dfs = (i: number) => {
if (i === n) {
res.push([...nums]);
}
for (let j = i; j < n; j++) {
[nums[i], nums[j]] = [nums[j], nums[i]];
dfs(i + 1);
[nums[i], nums[j]] = [nums[j], nums[i]];
}
};
dfs(0);
return res;
}


• /**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
const n = nums.length;
const ans = [];
const t = [];
const vis = new Array(n).fill(false);
function dfs(i) {
if (i >= n) {
ans.push([...t]);
return;
}
for (let j = 0; j < n; ++j) {
if (!vis[j]) {
vis[j] = true;
t.push(nums[j]);
dfs(i + 1);
vis[j] = false;
t.pop();
}
}
}
dfs(0);
return ans;
};


• public class Solution {
public IList<IList<int>> Permute(int[] nums) {
var ans = new List<IList<int>>();
var t = new List<int>();
var vis = new bool[nums.Length];
dfs(nums, 0, t, vis, ans);
return ans;
}

private void dfs(int[] nums, int i, IList<int> t, bool[] vis, IList<IList<int>> ans) {
if (i >= nums.Length) {
return;
}
for (int j = 0; j < nums.Length; ++j) {
if (!vis[j]) {
vis[j] = true;
dfs(nums, i + 1, t, vis, ans);
t.RemoveAt(t.Count - 1);
vis[j] = false;
}
}
}
}

• impl Solution {
fn dfs(i: usize, nums: &mut Vec<i32>, res: &mut Vec<Vec<i32>>) {
let n = nums.len();
if i == n {
res.push(nums.clone());
return;
}
for j in i..n {
nums.swap(i, j);
Self::dfs(i + 1, nums, res);
nums.swap(i, j);
}
}

pub fn permute(mut nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res = vec![];
Self::dfs(0, &mut nums, &mut res);
res
}
}