Permutation Generator

Given an array of distinct integers, return all possible permutations.

You are required to read the input from stdin and output the result to stdout. Each permutation should be printed on a new line with its numbers separated by a single space. The permutations must be output in lexicographically sorted order.

Formally, if the input array is \(A = [a_1, a_2, \dots, a_n]\), then you need to generate all sequences \(P = [p_1, p_2, \dots, p_n]\) that are permutations of \(A\). That is, every permutation \(P\) is a reordering of \(A\).

Constraints:

• \(0 \le n \le 6\) (Note: Although typically \(n \ge 1\), an empty list test case is also provided.)
• \(-10 \le a_i \le 10\)
• All integers in the array are unique.

inputFormat

The input consists of two parts:

1. An integer \(n\) in the first line indicating the number of elements in the array. (It can be 0.)
2. If \(n > 0\), the second line contains \(n\) space-separated integers representing the array.

Example:

3
1 2 3

outputFormat

Output all the permutations of the given array, one permutation per line. In each line, print the permutation as space-separated integers.

For an empty array (when \(n = 0\)), output a single empty line.

The order of output should be lexicographically sorted.

Example output for the above input:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

## sample

3
1 2 3

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

</p>