Print every arrangement (permutation) of the numbers 1 to n, in dictionary order: 1 2 3 comes before 1 3 2, which comes before 2 1 3.
What to build
A backtracking program that prints every permutation in dictionary order.
Requirements
- Fill positions one at a time, keeping track of which numbers are used.
- Try the numbers in increasing order at each position.
- Undo each choice after the recursive call.
Input
One number n (1 ≤ n ≤ 6).
Output
n! lines, each with one permutation, numbers separated by spaces.
Constraints
1 ≤ n ≤ 6.
Example
Input:
3
Output:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
Why it works
Trying smaller numbers first at each position means every arrangement with a smaller start is printed before one with a larger start, which is dictionary order.
Examples
Example 1 · Input
3
Expected output
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
Example 2 · Input
1
Expected output
1
Hints
Hint 1
Keep an array used[] and fill positions one at a time.
Hint 2
For position k, try the numbers 1 to n in increasing order, skipping used ones: mark, recurse to k + 1, unmark.
Hint 3
Trying smaller numbers first gives dictionary order without any sorting.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int n;
int perm[6];
int used[7];
void build(int k) {
if (k == n) {
for (int i = 0; i < n; i++) {
if (i > 0) printf(" ");
printf("%d", perm[i]);
}
printf("\n");
return;
}
for (int x = 1; x <= n; x++) {
if (used[x]) continue;
used[x] = 1;
perm[k] = x;
build(k + 1);
used[x] = 0; // undo the choice
}
}
int main(void) {
scanf("%d", &n);
build(0);
return 0;
}