perms[0] = {{{}, 1}};
perms[n_] :=
 Flatten[If[#2 == 1, Reverse, # &]@
     Table[{Insert[#1, n, i], (-1)^(n + i) #2}, {i, n}] & @@@
   perms[n - 1], 1];