Print Permutations

Moderate

0/80

2 upvotes

Asked in companies

Problem statement

Given an input string (STR), print all possible permutations of the input string.

Note:

The input string may contain the same characters, so there will also be the same permutations.
The order of permutations doesn’t matter.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The only input line contains a string (STR) of alphabets in lower case

Output Format:

Print each permutations in a new line

Constraint:

1<=length of STR<=8
Time Limit: 1sec

cba

abc
acb
bac
bca
cab
cba

Hint 1

Think about how you can break this problem between the first character of the string and the rest of it

Approaches (1)

Approach 1

Recursion

We can find all the permutations by Backtracking.

1:Fix a character then swap all the rest of the remaining character with a fixed character.

2:Then find all permutations for all remaining characters by the recursive call.

3:The base case for the recursion will be when there is only one character left unprocessed.

Below is the illustration to approach.

Time Complexity

O(N*N!), where N is the length of the String.

There will N! Recursion call and For each permutation, it requires O(N) time to print.

Space Complexity

O(N!), where N is the length of the string

Since there is N! Recursive calls of recursion. I.e stack

(100% EXP penalty)

Print Permutations

Console