String recursion in Rust

In Rust, I am trying to obtain all possible combinations of a-z characters up to a fixed length with no repeating letters.

For example, for a limited set of a-f and a length of 3 I should get:

abc
abd
abe
abf
acb
acd
ace
acf
adb
… etc

I’ve been struggling to do this through recursion and have been banging my head on ownership and borrows. The only way I’ve managed to do it is as follows, but this is cloning strings all over the place and is very inefficient. There are probably standard permutation/combination functions for this in the standard library, I don’t know, but I’m interested in understanding how this can be done manually.

fn main() {
    run(&String::new());
}

fn run(target: &String) {
    for a in 97..123 { // ASCII a..z
        if !target.contains(char::from(a)) {
            let next = target.clone() + char::from(a).to_string().as_str(); // Working but terrible
            if next.len() == 3 { // Required string size
                println!("{}", next);
            } else {
                run(&next);
            }
        }
    }
}

Any help would be much appreciated.

>Solution :

First off, a couple of remarks:

• &String is kind of an anti-pattern that is rarely seen. It serves no purpose; all the functionality that String has over str requires mutability. So it should either be &mut String or &str.
• 97..123 is uncommon … use 'a'..='z'.

Now to the actual problem:

As long as you pass a non-mutable string into the recursion, you won’t get around cloning the data. I’d make the string mutable, then you can simply append and remove single characters from it.

Like this:

fn main() {
    run(&mut String::new());
}

fn run(target: &mut String) {
    for a in 'a'..='z' {
        if !target.contains(a) {
            target.push(a);
            if target.len() == 3 {
                // Required string size
                println!("{}", target);
            } else {
                run(target);
            }
            target.pop();
        }
    }
}