Generate all permutations of {1, 2, 3, 4} by backtracking.
Start with an empty permutation and an empty set of unused numbers: [], {1, 2, 3, 4} Choose a number from the unused set: 1 Add the chosen number to the current permutation: [1] Recursively generate permutations with the remaining unused numbers: [1], {2, 3, 4} Backtrack by removing the chosen number from the current permutation and adding it back to the unused set: [], {1, 2, 3, 4}
Start with an empty permutation and an empty set of unused numbers: [], {1, 2, 3, 4} Choose a number from the unused set: 2 Add the chosen number to the current permutation: [2] Recursively generate permutations with the remaining unused numbers: [2], {1, 3, 4} Backtrack by removing the chosen number from the current permutation and adding it back to the unused set: [], {1, 2, 3, 4}
Start with an empty permutation and an empty set of unused numbers: [], {1, 2, 3, 4} Choose a number from the unused set: 3 Add the chosen number to the current permutation: [3] Recursively generate permutations with the remaining unused numbers: [3], {1, 2, 4} Backtrack by removing the chosen number from the current permutation and adding it back to the unused set: [], {1, 2, 3, 4}
Start with an empty permutation and an empty set of unused numbers: [], {1, 2, 3, 4} Choose a number from the unused set: 4 Add the chosen number to the current permutation: [4] Recursively generate permutations with the remaining unused numbers: [4], {1, 2, 3} Backtrack by removing the chosen number from the current permutation and adding it back to the unused set: [], {1, 2, 3, 4}
Start with an empty permutation and an empty set of unused numbers: [], {1, 2, 3, 4} Choose a number from the unused set: 1 Add the chosen number to the current permutation: [1] Recursively generate permutations with the remaining unused numbers: [1], {2, 3, 4} Choose a number from the unused set: 2 Add the chosen number to the current permutation: [1, 2] Recursively generate permutations with the remaining unused numbers: [1, 2], {3, 4} Choose a number from the unused set: 3 Add the chosen number to the current permutation: [1, 2, 3] Recursively generate permutations with the remaining unused numbers: [1, 2, 3], {4} Choose a number from the unused set: 4 Add the chosen number to the current permutation: [1, 2, 3, 4] This is a valid permutation.
Continue the process by exploring other branches and combinations until all permutations are generated.
The generated permutations are:
[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 3, 2]
[1, 4, 2, 3]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 3, 1]
[2, 4, 1, 3]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 2, 3, 1]
[4, 2, 1, 3]
[4, 3, 2, 1]
[4, 3, 1, 2]
[4, 1, 3, 2]
[4, 1, 2, 3]