ADVANCED
Q1. Print all the permutations of a string.
public class Recursion3 {
public static void printPermutation(String str, int idx, String perm) {
if([Link]() == 0) {
[Link](perm);
return;
}
for(int i=0; i<[Link](); i++) {
char currChar = [Link](i);
String newStr = [Link](0, i) + [Link](i+1);
printPermutation(newStr, idx+1, perm+currChar);
}
}
public static void main(String args[]) {
String str = "abc";
printPermutation(str, 0, "");
}
}
Time complexity - O(n*n!)
Q2. CountPathMaze
public class Recursion3 {
public static int countPaths(int i, int j, int m, int n) {
if(i == m-1 || j == n-1) {
return 1;
}
return countPaths(i+1, j, m, n) + countPaths(i, j+1, m, n);
}
public static void main(String args[]) {
int m = 4, n = 5;
[Link](countPaths(0, 0, m, n));
}
}
Time complexity - O(2^(m+n))
Q3. Tiling problem
public class Recursion3 {
public static int placeTiles(int n, int m) {
if(n < m) {
return 1;
} else if(n == m) {
return 2;
}
return placeTiles(n-1, m) + placeTiles(n-m, m);
}
public static void main(String args[]) {
int n = 4, m = 4;
[Link](placeTiles(n, m));
}
}
Q4. Friends pairing problem
public class Recursion3 {
public static int pairFriends(int n) {
if(n <= 1) {
return 1;
}
return pairFriends(n-1) + (n-1) * pairFriends(n-2);
}
public static void main(String args[]) {
int n = 3;
[Link](pairFriends(n));
}
}
Q5. Subsets of a set
import [Link];
public class Recursion3 {
public static void printSubsets(ArrayList<Integer> subset) {
for(int i=0; i<[Link](); i++) {
[Link]([Link](i)+" ");
}
[Link]();
}
public static void findSubsets(int n, ArrayList<Integer> subset) {
if(n == 0) {
printSubsets(subset);
return;
}
findSubsets(n-1, subset);
[Link](n);
findSubsets(n-1, subset);
[Link]([Link]() - 1);
}
public static void main(String args[]) {
int n = 3;
findSubsets(n, new ArrayList<Integer> ());
}
}