Say we have a set [1,2,3], its permutations are [ [ 3, 2, 1 ], [ 2, 3, 1 ], [ 2, 1, 3 ], [ 3, 1, 2 ], [ 1, 3, 2 ], [ 1, 2, 3 ] ]。

It's very easy to understand what permutation is, but the problem is how to get them.

Let's take a set [1,3,5] as an example, here is the process:

[[]] =>
[[1]] =>
[[3,1], [1,3]] =>
[[5,3,1],[3,5,1],[3,1,5], [5,1,3],[1,5,3],[1,3,5]]

We can see clearly that we start with a queue with an empty array element. Loop the queue, and insert new set element into all the positions of the current queue element. For example, if current queue element is [3,1], new set element is 5, then we insert 5 in all positions and then we get [5,3,1], [3,5,1], [3,1,5]。

Let's use this process to solve the leetcode Permutations problem.

function permute(nums: number[]): number[][] {
    let q: number[][] = [[]];
    for (const num of nums) {
        const end = q.length;
        for (let i = 0; i < end; i++) {
            for (let j = 0; j <= q[i].length; j++) {
                const copy = q[i].slice();
                copy.splice(j, 0, num);
                q.push(copy);
            }
        }
        q = q.slice(end); // note here, discard the previous temporary element
    }
    return q;
};