Dictionary order smaller using recursion

#1

output is correct only…but all test cases failing

#2

Hey @hg11110000
Mentioned the changes in comments : https://ide.codingblocks.com/s/365077 :slight_smile:
For
“cba”
output should be

abc
acb
bac
bca
cab

but ur code was giving

cab
bca
bac
abc
acb

#3

output is correct…even passes test cases but in some test cases show tle ???

#4

@Kartikkhariwal1
…

#5

Hey @hg11110000
You are using multiset that’s why its showing TLE .
You don’t have to use any STL in it.

#6

N=10 so N! permutations ,In worstcase we push all of them in set
Which makes complexity ( (N!)Log(N!) )

#7

No STL used…then also TLE :frowning:
@Kartikkhariwal1

#8

Bro complexity still remains same ,
You are pushing N! permutations in array and then sorting it which makes complexity ( (N!)Log(N!) )

#9

@Kartikkhariwal1

not able to understand ur code…
why we need to sort ?
why backtracking step removed
why extra string etc ???

can u explain me more please ?

#10

Because we need to print in sorted order

From
ABC 0
We woul like to replace and call
ABC 1
BAC 1
BCA 1
If u backtrack it will call
ABC 1
BAC 1
CBA 1

Since arrays are passed by reference any change u do in recyrsive calls will be reflected back so to not reflect that difference we copy string earlier and then reinitialize it before returning

Do a dry run for some thre character string and you will be able to understand in more detail