• # Explanation

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

1. We know there are `n!` possible permutations for `n` elements.
2. 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:

1. Build a list of all elements in ascending order.
The length of this list is `n` (i.e. not the original input size).
2. 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.
3. Append the selected element to the result, i.e. the next element in the `k`th permutation.
4. Remove the selected element from the list.
5. 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) {
}
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];
k %= f;
}
return result;
}
List<Integer> toList(int[] nums) {
for (int num : nums) {
}
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) {
}
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();
} 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;
}``````

• Yes, you can easily make `permutation` O(n):

``````List<Integer> permutation(int[] nums, int k) {
int[] source = nums.clone();
int len = nums.length;
List<Integer> result = new ArrayList(len);
while (len-- > 0) {
int f = FACT[len];
source[k / f] = source[len];
k %= f;
}
return result;
}
``````

• Didn't run it, but that seems to shuffle the result...

What if `k/f` gives index `0` twice in a row and `source` contains `[1,2,3,4,5]`? First index `0` points to `1`, then `source` becomes `[5,2,3,4,5]` (last `5` ignored by `len--`) and second index `0` points to `5` instead of `2`.

• Yes, it enumerates differently, but since we're not asked for a specific order, that's fine.

• Ah, I carried over the lexicographical order from "Next Permutation" which I did just before this. Nice, thanks for the tip!

• In the line "Now the list has one less elements and we can repeat from Step 2 with k' = k % n!..."

k' = k % n! should be K' = k%(n-1)!

• Yeah, I thought it might be confusing, it's hard to express timeliness in plain text algorithms. Notice that the sentence you quoted contains "now the list has one less elements" and above at point 1.:

The length of this list is n (i.e. not the original input size).

... so `n` is already `n-1`. Let me know if you know how to make it more clear.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.