# Printing all permutations

Question: Print all permutations of a String iteratively.

Related Tags:

## Questions

• Do we permute the repeated chars as well?

Assume that we permute the repeated chars as well, so that an input such as `qqq` should still return six results.

## Recursive Solution

In a recursive solution, we create a method with two parameters - one storing the prefix, and one storing the rest of the string, `s`. The algorithm pseudocode is written below.

1. If our string length is zero, print out the prefix.
2. If our string length is not zero, recursively call the permutation algorithm appending a char at the `prefix`, and the original string without its front char removed.
``````static void permRecursive(String prefix, String s) {

if (s.length() == 0) {
System.out.println(prefix);
} else {
// for each char in String s, add to prefix
for (int i = 0; i < s.length(); i++) {
permutations(prefix + s.charAt(i),
s.substring(0,i) + s.substring(i+1));
}
}
}
``````

Here's a stack trace of what's going on when you call `permRecursive("", "ABCD");`. The left side will be the prefix, and right side will be the String.

``````ABCD      // initial
A BCD
AB CD
ABC D
ABCD      // No more s so print ABCD
-----
AB CD     // Step back to AB CD case, but now take the next char (D) into prefix
ABD C
ABDC      // Print ABDC
-----
A BCD     // Step back to A BCD case, appending the next char (C) into prefix
AC BD
ACB D
ACBD      // print ACBD
-----
AC BD     // Step back to AC BD case, appending the next char (D) into prefix
ACD B
ACDB      // print ACDB
-----
// and so on..``````

## Algorithm Implementation in Java

``````public class Permutations {
public static void main(String[] args) {
permRecursive("", "ABCD");
}

static void permRecursive(String prefix, String s) {

if (s.length() == 0) {
System.out.println(prefix);
} else {
// for each char in String s, add to prefix
for (int i = 0; i < s.length(); i++) {
permutations(prefix + s.charAt(i),
s.substring(0,i) + s.substring(i+1));
}
}
}
}``````

Came up with a better solution or have a question? Comment below!

Next Challenge: