Steps of Backtracking to find all permutations of {1,2,3}
Crossed out values like this indicate what changes from
Sk→ Sk+1
Rows of all ø indicate backtrack steps (because Sk is
empty).
| a1=1 |
S1={1,2,3} |
→ |
S2={2,3} |
| a2=2 |
S2={2,3} |
→ |
S3={3} |
| *a3=3 |
S3={3} |
→ |
S4={ø} |
| a4=ø |
ø |
→ |
ø |
| a3=ø |
ø |
→ |
ø |
| a2=3 |
S2={3} |
→ |
>S3={2*} |
| *a3=2 |
S3={2} |
→ |
>S4={ø} |
| a4=ø |
ø |
→ |
ø |
| a3=ø |
ø |
→ |
ø |
| a2=ø |
ø |
→ |
ø |
| a1=2 |
S1={2,3} |
→ |
>S2={1*,3} |
| a2=1 |
S2={1,3} |
→ |
>S3={3} |
| *a3=3 |
S3={3} |
→ |
>S4=ø |
| a4=ø |
ø |
→ |
ø |
| a3=ø |
ø |
→ |
ø |
| a2=3 |
S2={3} |
→ |
>S3={1*} |
| *a3=1 |
S3={1} |
→ |
>S4=ø |
| a4=ø |
ø |
→ |
ø |
| a3=ø |
ø |
→ |
ø |
| a2=ø |
ø |
→ |
ø |
| a1=3 |
S1={3} |
→ |
>S2={1*,2*} |
| a2=1 |
S2={1,2} |
→ |
>S3={2} |
| *a3=2 |
S3={2} |
→ |
>S4=ø |
| a4=ø |
ø |
→ |
ø |
| a3=ø |
ø |
→ |
ø |
| a2=2 |
S2={2} |
→ |
>S3={1*} |
| *a3=1 |
S3={1} |
→ |
>S4=ø |
| a4=ø |
ø |
→ |
ø |
| a3=ø |
ø |
→ |
ø |
| a2=ø |
ø |
→ |
ø |
| a1=ø |
ø |
→ |
ø |
|
DONE!
|