46. Permutations
Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
@tag-backtracking

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.