# Explanation

The general idea is the following (same as other solutions):

- We know there are
`n!`

possible permutations for`n`

elements. - Enumerate them one by one

Most solutions use the previous permutation to generate the next permutation or build it recursively.

I had the idea to calculate the `k`

^{th} permutation directly from the input. Steps are as follows:

- Build a list of all elements in ascending order.

The length of this list is`n`

(i.e. not the original input size). - Given
`k`

we know what the first element will be in the`k`

^{th}permutation of the current list.

There are`n`

groups in the lexicographical order of all permutations of the list. Inside a group each permutation's first element is the same. Each group has`(n-1)!`

elements, so an easy`k / (n-1)!`

will give us the index. - Append the selected element to the result, i.e. the next element in the
`k`

^{th}permutation. - Remove the selected element from the list.
- Now the list has one less elements and we can
**repeat from Step 2**with`k' = k % n!`

,

that is the`k'`

^{th}permutation of the reduced list.

Notice that it doesn't matter what the elements are because the indices are calculated.

# Examples for `n = 1...4`

```
elements k indices
[] - - =----- trivial
[1] 0 0 =----- reduces to [] after selecting 1
[1,2] 0 0 0 =----- reduces to [2] after selecting 1
[2,1] 1 1 0 =----- reduces to [1] after selecting 2
[1,2,3] 0 0 0 0 =\____ reduces to [2,3] after selecting 1
[1,3,2] 1 0 1 0 =/
[2,1,3] 2 1 0 0 =\____ reduces to [1,3] after selecting 2
[2,3,1] 3 1 1 0 =/
[3,1,2] 4 2 0 0 =\____ reduces to [1,2] after selecting 3
[3,2,1] 5 2 1 0 =/
[1,2,3,4] 0 0 0 0 0 =\
[1,2,4,3] 1 0 0 1 0 \
[1,3,2,4] 2 0 1 0 0 \__ reduces to [2,3,4] after selecting 1
[1,3,4,2] 3 0 1 1 0 /
[1,4,2,3] 4 0 2 0 0 /
[1,4,3,2] 5 0 2 1 0 =/
[2,1,3,4] 6 1 0 0 0 =\
[2,1,4,3] 7 1 0 1 0 \
[2,3,1,4] 8 1 1 0 0 \__ reduces to [1,3,4] after selecting 2
[2,3,4,1] 9 1 1 1 0 /
[2,4,1,3] 10 1 2 0 0 /
[2,4,3,1] 11 1 1 1 0 =/
[3,1,2,4] 12 2 0 0 0 =\
[3,1,4,2] 13 2 0 1 0 \
[3,2,1,4] 14 2 1 0 0 \__ reduces to [1,2,4] after selecting 3
[3,2,4,1] 15 2 1 1 0 /
[3,4,1,2] 16 2 2 0 0 /
[3,4,2,1] 17 2 2 1 0 =/
[4,1,2,3] 18 3 0 0 0 =\
[4,1,3,2] 19 3 0 1 0 \
[4,2,1,3] 20 3 1 0 0 \__ reduces to [1,2,3] after selecting 4
[4,2,3,1] 21 3 1 1 0 /
[4,3,1,2] 22 3 2 0 0 /
[4,3,2,1] 23 3 2 1 0 =/
```

# Code

**The fact of FACT**: since the problem asks for

**all**permutations we can be sure it won't ask for more than

`12`

elements, because `13!`

is out of range for `int`

and all lists are indexed by `int`

s. Also `12!`

permutations of `12`

elements in `List<List>`

is good `7GiB`

worth of memory.```
public class Solution {
private static final int[] FACT = { // 479001600 < 2147483647 < 6227020800
1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 39916800, 479001600
};
public List<List<Integer>> permute(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>(nums.length);
for (int k = 0; k < FACT[nums.length]; ++k) {
result.add(permutation(nums, k));
}
return result;
}
List<Integer> permutation(int[] nums, int k) {
// k %= FACT[nums.length]; // in case you want to use it elsewhere
List<Integer> source = toList(nums);
List<Integer> result = new ArrayList(nums.length);
while (!source.isEmpty()) {
int f = FACT[source.size() - 1];
result.add(source.remove(k / f));
k %= f;
}
return result;
}
List<Integer> toList(int[] nums) {
List<Integer> result = new LinkedList<>();
for (int num : nums) {
result.add(num);
}
return result;
}
}
```

# Analysis

It's clear that we need to iterate `n!`

times, because we're generating `n!`

elements.

The `permutation`

method looks like `O(n)`

, but sadly it's `O(n^2)`

because `remove`

takes `O(n)`

:

`LinkedList`

`i`

steps to find the`i`

^{th}element and`O(1)`

to remove it`ArrayList`

`O(1)`

to find the`i`

^{th}element and`n-i`

steps to remove the`i`

^{th}element- keep
`int[] nums`

and`boolean[] removed`

we have to iterate over each removed item, so`O(n)`

`Map<Integer, Integer>`

may be better, but we have to re-index all remaining elements**Is there a better data structure for this?**

# Code variations

In case you don't like the hardcoded `FACT`

:

```
/* 12! = 479001600 < Integer.MAX_VALUE = 2147483647 < 13! = 6227020800 */
private static final int[] FACT = factorials(12);
static int[] factorials(int n) {
int[] f = new int[n+1];
f[0] = f[1] = 1;
for (int i = 2; i <= n; ++i) {
f[i] = f[i-1] * i;
}
return f;
}
```

or it's even possible to calculate `n!`

only once and keep reducing it, but then we have to pass an extra unrelated argument.

```
public List<List<Integer>> permute(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>(nums.length);
int fact = factorial(nums.length);
for (int k = 0; k < fact; ++k) {
result.add(permutation(nums, fact, k));
}
return result;
}
List<Integer> permutation(int[] nums, int f, int k) {
if (nums.length == 0) return Collections.emptyList();
List<Integer> source = toList(nums);
List<Integer> result = new ArrayList(nums.length);
do {
k %= f;
f /= source.size();
result.add(source.remove(k / f));
} while (!source.isEmpty());
return result;
}
static int factorial(int n) {
if (n <= 1) return 1;
int result = n;
while (--n > 1) {
result *= n;
}
return result;
}
```