# Write a program to print all permutations of a given string with repetition. (Repetition of characters is allowed).

### Given a string of length n, print all permutation of the given string. Repetition of characters is allowed

Case 1
Input:   A
output: A

Case 2
Input: AB
output:
AA
AB
BA
BB

Case 3
Input:  ABC
output:
AAA
AAB
AAC
ABA
ABB
ABC
ACA
ACB
ACC
BAA
BAB
BAC
BBA
BBB
BBC
BCA
BCB
BCC
CAA
CAB
CAC
CBA
CBB
CBC
CCA
CCB
CCC

### Algorithm:

How many permutations is possible?

Lets see how many permutation is possible for given n character String.
In string "AB", n is 2
In string "ABC", n is 3
From above permutations displayed, we can see relation as n^n.
So for "AB", total permutations are 2^2 = 4.
For "ABC", total permutations are 3^3 = 27. How to print all permutation?

It is very easy, Lets take an example of String "ABC"

We will take recursive approach. In this approach important thing is base case.
We will try to make each permutation by adding characters one by one to the temporary String
that need to be printed.

As our string is of length 3, so we will add the characters to the temporary string that needs
to be printed till the length is 3 as permutation string length will be 3.

So base case is, when the length of our temporary string that needs to be printed is 3,
print and return.

Now, how we will form temporary string is,
add first character of string to temporary string and check the length of
temporary string which is less then 3, true, so call function again,
tempString = "A"

add first character of string to temporary string and check the length of
temporary string which is less then 3, true, so call function again,
tempString = "AA"

add first character of string to temporary string and check the length of
temporary string which is less then 3, false, so print and return
tempString = "AAA"

1st permutation is AAA
after returning from printing 1st permutation, tempString will be again "AA"

Now appending "B" to "AA" will make our 2nd permutation that is "AAB", print and return.
Now appending "C" to "AA" will make our 3rd permutation that is "AAC", print and return.

from this we can see, that keeping "AA" common and adding "A", "B", "C" that is
each character of String, we are getting permutation.
if we continue the same for 2nd position and then for 1st position of temporary string then
we will get all our permutations.

### Java Program to print permutation of string with repetition

```package backtracking;

public class StringPermutationWithRepetition {

public static void main(String[] args) {
printPermutationOfStrings("ABC");
}

private static void printPermutationOfStrings(String str){
printPermutation(str, "");
}

private static void printPermutation(String str, String stringToPrint){
if(stringToPrint.length()==str.length()){
System.out.println(stringToPrint);
return;
}
for (int i = 0; i < str.length(); i++) {
printPermutation(str, stringToPrint + str.charAt(i));
}
}
}

```

### You may also like to see

#### Print all subsets of a given set.

Enjoy !!!!

If you find any issue in post or face any error while implementing, Please comment.