Menu
Method 1(Using Recursion) :Create a recursive function say permute(string s, int l, int r), and pass string along with starting index of the string and the ending index of the string. Base condition will be if(l==r) then print the s. Otherwise, run a loop from [l, r] And, swap(s[l], s[i])
A Permutation of a string is another string that contains same characters, only the order of characters can be different. For example, “abcd” and “dabc” are Permutation of each other.
I came across THIS post which tried very hard to explain the recursive solution to print all string.
public class Main {
private static void permutation(String prefix, String str) {
int n = str.length();
if (n == 0)
System.out.println(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i),
str.substring(0, i) + str.substring(i + 1));
}
}
public static void main(String[] args) {
permutation("", "ABCD");
}
}
But still I am not able to get the part when we start popping off the stack. For example, recursion goes all the way till permutation("ABCD",""), where base case meets and it prints ABCD. But what happens now? We pop off permutation("ABC","D") from function call stack. What we do with this and so on?
Can someone please help explain a bit?
Also, I need some pointers on the time complexity of this. Not like complete calculation but some hints.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With