This problem need the permutations in lexicographic order, here is the recursion method. When n is 4, we list out the result.

1234 2134 3124 4123

1243 2143 3142 4132

1324 2314 3214 4213

1342 2341 3241 4231

1423 2413 3412 4312

1432 2431 3421 4321

The first column is the permutation begin with 1. For n elements permutation, the last permutation begin with 1 is 1n(n-1)...432. We swap the minimum among n(n-1)...432 with first number, that is swap the last one(here is 2) with first number, we get 2n(n-1)...431. Then reverse the last n - 1 number, we get 2134...(n-1)n, this is first permutation begin with 2. Now we enter the second column.

The second column is the permutation begin with 2. The last permutation begin with 2 is 2n(n-1)...431, we swap the minimum among n(n-1)...431 with first number, but because 1 is the first number before, so we swap the second last one (here is 3) with first number, we get 3n(n-1)...421. Then reverse the last n - 1 number, we get 312...(n-1)n, this is the first permutation begin with 3. Now we enter the third column.

The third column is the permutation begin with 3. The last permutation begin with 3 is 3n(n-1)...421, we swap the minimum among n(n-1)...421 with first number, but because 1 and 2 are the first number before, so we swap the third second last one(here is 4) with first number, we get 4n(n-1)...321. Then reverse the last n - 1 number, we get 412...(n-1)n, this is the first permutation begin with 4. Now we enter the fourth column.

So we get a recursion solution.

step 1: i = n

step 2: get the permutations of last n -1 number recursion

step 3: swap the nth number with the first number

step 4: i--

step 5: reverse the last n - 1 number

step 6: go to step 2

The terminal condition is i is the first number.

Notice:

At the end, we need reverse the array to ensure not change the array.

```
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums.length == 0)
return result;
permute(nums, 0, result);
reverse(nums, 0, nums.length - 1); //after permutation, we need to reverse array
return result;
}
public static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void reverse(int[] nums, int begin, int end) {
while (begin < end) {
swap(nums, begin, end);
begin++;
end--;
}
}
private static void permute(int[] nums, int start, List<List<Integer>> result) {
if (start == nums.length - 1) {
List<Integer> temp = new ArrayList<Integer>();
for (int i = 0; i < nums.length; i++) {
temp.add(nums[i]);
}
result.add(temp);
return;
}
int i = nums.length;
while (i > start) {
permute(nums, start + 1, result);
swap(nums, start, i - 1);
i--;
if (i <= start)
break;
reverse(nums, start + 1, nums.length - 1);
}
}
```