I was very much confused, because you said "reverse" instead of "recurse" in your initial post at one point. So I was assuming there was some complicated problem statement missing. Okay.
The key is to keep track of what you haven't added. See how the tree stems apart, and what data you want to keep track of. This algorithm can be proven qualitatively by drawing the trees. It can be proven mathematically by subproblems and dynamic programming. I'll leave that excercise up to you.
Edit: In reference to your question about doing it without copying new strings: I do not believe so. This is due to the nature of dynamic programming and subproblems. If you look at the tree the reason becomes obvious. But there might be some fancy ways. Such as brute forcing it iteratively, and checking for invalid entries. So I doubt any other solutions would be efficient in any case. But I am not sure.
Here it is in C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void permutate(char *s, char *r, int k, int n) {
int i;
char *new_s;
if (k==n) { // At the end
r[n] = 0; // Add a null terminator
printf("%s\n", r); // Output result
return;
}
for(i=0;i<n;i++) {
if (s[i]) {
new_s = calloc(sizeof(char), n);
// Use memcpy to ignore the null terminators
memcpy(new_s, s, sizeof(char) * (n+1));
new_s[i] = 0; // Mark used character
r[k] = s[i]; // Store used character
permutate(new_s, r, k+1, n);
free(new_s);
}
}
}
int main() {
char str[] = "abc";
char *result_str = calloc(sizeof(char), strlen(str) + 1);
permutate(str, result_str, 0, strlen(str));
return 0;
}