Friends Pairing  2
1. You are given an integer n, which represents n friends numbered from 1 to n.Input Format
2. Each one can remain single or can pair up with some other friend.
3. You have to print all the configurations in which friends can remain single or can be paired up.
Note > Check out the question video and write the recursive code as it is intended without
changing signature. The judge can't force you but intends you to teach a concept.
A number nOutput Format
Check the sample ouput and question video.Question Video
1 <= n <= 10Sample Input
3Sample Output
1.(1) (2) (3)
2.(1) (2,3)
3.(1,2) (3)
4.(1,3) (2)

Editorial
Let us go through the rules again. We cannot make 2 different permutations like 12 and 21. Only 12 is valid.
We will solve this question by recursion and backtracking. At levels, we will place nth person.
We will explore the options available at the nth level.
For example, for n = 3, we will start from level 1. 1 has the choice to choose from 2 and 3 or be alone. For next level, 2 will be have the option to choose from 3 or be alone and so on. If 1 chose 2, then 2 will have no choice (as it is already chosen) but to make the call for the next n.
At node pre, we will mark the current friend as visited and at node post we will mark the current friend as unvisited.
When we are at level 1, to choose from 2,3,....n we will use a for loop. Before calling the recursive function in the FOR loop for the next level, we will mark the friend that we want to pair up with as visited (edge pre) and after the calling the recursive, we will unmark that friend (edge post).
Signature:
public static void solution (int i, int n, boolean[] used, String asf){}
i = current level (friend)
n = user input
used  an array to store which array have been used.
asf  string to store the answer till the current level.
Code:
static int counter = 1; public static void solution(int i, int n, boolean[] used, String asf) { if (i > n) { System.out.println(counter + "." + asf); counter++; return; } if (used[i]) { solution(i + 1, n, used, asf); } else { used[i] = true; solution(i + 1, n, used, asf + "(" + i + ") "); for (int j = i + 1; j <= n; j++) { if (used[j] == false) { used[j] = true; solution(i + 1, n, used, asf + "(" + i + "," + j + ") "); used[j] = false; } } used[i] = false; } }
java false
Code Explained:
We have two options, whether to pair the current friend or not.
At node pre, we mark the current friend (i) as visited.
OPTION 1  Not pairing the current friend  we make a call for the next friend.
OPTION 2  Pairing the current friend  we use a loop from current friend + 1 till n (to avoid permutations). If the option has not been paired already, we pair it with the current friend and call the recursive function for the next friend. At edge pre we will mark the options that are valid as visited and at edge post we will mark them as univisted.
We also have to check whether the current friend (current level) has already been paired before or not. If it has been paired, we will directly call the recursive function for the next friend.
For example  If we pair 2 with 1, then when we call recursive function for 2, as it has been already paired, we would not do anything for that level and call the recursion function for the next level.
At node post, we will mark the current friend (i) as unvisited.
Base Case:
When i will be greater than n, it means that we have made all the pairs for n friends.
To match the way the output is required, we will use a counter and print the asf as the output is required and return.
Dry Run:

Asked in Companies

Related Topics