problema recursividad

[gustavoh10]

Gente como andan!
Tengo un problema que seguro es una pavada, pero la verdad
que nos esta poniendo los pelos de puntas a mi y a unos
amigos.
Paso a describir el inconveniente.
Tengo un lista de lugares en un array. Digamos
1 LSM
2 Crespo
3 Diamante
4 Paraná
5 Valle Maria

y quiero armar un arbol para que me quede de esta forma. (los
diferentes caminos posibles para recorrer las ciudades)

1 <-(punto de partida)
2 3 4 5
2 3 5 4
2 4 3 5
2 4 5 3
2 5 3 4
2 5 4 3
3 2 4 5
3 2 5 4
...
...
5 4 3 2

los número representan las ciudades por las que paso. Tendria
que armar todos los caminos posibles pasando solo una vez por cada
ciudad.
En este caso me quedan 24 caminos posibles

etc, etc...
La verdad que la unica forma que se nos ocurrio es haciendo
recursividad, pero estamos teniendo problemas para empezar.
Alguien podria darnos una patadita para poder empezar. jeje!!!
Gracias!