###
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

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

#### Print all combinations/permutations of a string of length k that can be formed from a set of n characters.

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

**Enjoy !!!!**

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

## Post a Comment