Redirecting to
NADOS

Friends Pairing - 2

  Prev   Next

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given an integer n, which represents n friends numbered from 1 to n.
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.
Input Format 
A number n
Output Format 
Check the sample ouput and question video.
Question Video
Constraints 
1 <= n <= 10
Sample Input 
3
Sample 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 1-2 and 2-1. Only 1-2 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






Video Solution

Code Solution

Run
 
Run
Id Name