Count possible combinations of pairs with adjacent elements from first N numbers

0 0 6 minutes read

Given a number N, the task is to count all possible combinations of pairs formed using adjacent elements.
Note: If an element exists already in a pair, it cannot be picked in the next pair. For example: for {1,2,3}: {1,2} and {2,3} will not be considered as a correct combination.
Examples:

Input : N = 4
Output : 5
Explanation : If N = 4, the possible combinations are:
{1}, {2}, {3}, {4}
{1, 2}, {3, 4}
{1}, {2, 3}, {4}
{1}, {2}, {3, 4}
{1, 2}, {3}, {4}

Input : N = 5
Output : 8

Approach : Break the problem into smaller subproblems. If there are N numbers, and there are two cases either a number is alone, or it is in a pair, if a number is alone, find the ways of pairing (n-1) numbers left, or if it is in a pair, find the ways of pairing (n-2) numbers left. If there are just 2 numbers left they can generate 2 combinations either alone or in a pair, and if a single number is left it will be in singleton, so there is just 1 combination.
Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
// Function to count the number of ways
int ways(int n)
{
    // If there is a single number left 
    // it will form singleton
    if (n == 1) {
        return 1;
    }
    // if there are just 2 numbers left, 
    // they will form a pair
    if (n == 2) {
        return 2;
    }
    else {
        return ways(n - 1) + ways(n - 2);
    }
}
 
// Driver Code
int main()
{
    int n = 5;
 
    cout << "Number of ways = " << ways(n);
 
    return 0;
}

Java

/*package whatever //do not write package name here */
import java.io.*;
 
class GFG
{
     
// Function to count the number of ways
static int ways(int n)
{
    // If there is a single number left 
    // it will form singleton
    if (n == 1) 
    {
        return 1;
    }
     
    // if there are just 2 numbers left, 
    // they will form a pair
    if (n == 2) 
    {
        return 2;
    }
    else
    {
        return ways(n - 1) + ways(n - 2);
    }
}
 
// Driver Code
public static void main (String[] args) 
{
    int n = 5;
     
    System.out.println("Number of ways = " + ways(n));
}
}

Python3

# Python3 code implementation of the above program
 
# Function to count the number of ways 
def ways(n) :
     
    # If there is a single number left 
    # it will form singleton 
    if (n == 1) :
        return 1; 
     
    # if there are just 2 numbers left, 
    # they will form a pair 
    if (n == 2) :
        return 2; 
     
    else :
        return ways(n - 1) + ways(n - 2); 
 
# Driver Code 
if __name__ == "__main__" : 
 
    n = 5; 
 
    print("Number of ways = ", ways(n)); 
 
# This code is contributed by AnkitRai01

C#

// C# implementation of the above code
using System;
 
class GFG 
{ 
     
// Function to count the number of ways 
static int ways(int n) 
{ 
    // If there is a single number left 
    // it will form singleton 
    if (n == 1) 
    { 
        return 1; 
    } 
     
    // if there are just 2 numbers left, 
    // they will form a pair 
    if (n == 2) 
    { 
        return 2; 
    } 
    else
    { 
        return ways(n - 1) + ways(n - 2); 
    } 
} 
 
// Driver Code 
public static void Main() 
{ 
    int n = 5; 
     
    Console.WriteLine("Number of ways = " + ways(n)); 
} 
} 
 
// This code is contributed by AnkitRai01

Javascript

<script>
    // Javascript implementation of the above code
     
    // Function to count the number of ways 
    function ways(n) 
    { 
        // If there is a single number left 
        // it will form singleton 
        if (n == 1) 
        { 
            return 1; 
        } 
 
        // if there are just 2 numbers left, 
        // they will form a pair 
        if (n == 2) 
        { 
            return 2; 
        } 
        else
        { 
            return ways(n - 1) + ways(n - 2); 
        } 
    }
     
    let n = 5; 
       
    document.write("Number of ways = " + ways(n)); 
 
// This code is contributed by suresh07.
</script>

Output:

Number of ways = 8

Time Complexity: O(2^N)
Auxiliary Space: O(N)

Another Approach:

We can store the computed values in an array and reuse the computed value afterwords which would make the program efficient.

Implementation of the above approach:

C++

// C++ implementation of the above approach 
 
#include <bits/stdc++.h>
using namespace std;
 
// vector to store the computed values
vector<int> dp;
 
// Function to count the number of ways
int ways(int n)
{
    // If there is a single number left 
    // it will form singleton
      int& res = dp[n];
       
      // return the stored value
      // if the value is already computed
      if(res!=-1)
          return res;
   
      // base case
    if (n == 1) {
        return res=1;
    }
   
    // if there are just 2 numbers left, 
    // they will form a pair
    if (n == 2) {
        return res=2;
    }
    else {
           
        return res = ways(n - 1) + ways(n - 2);
    }
}
 
// Driver Code
int main()
{
    int n = 5;
    dp = vector<int>(n + 1,-1);
    cout << "Number of ways = " << ways(n);
 
    return 0;
}

Java

// Java implementation of the above approach
 
class GFG {
 
    // vector to store the computed values
    static int[] dp;
 
    // Function to count the number of ways
    static int ways(int n)
    {
        // If there is a single number left
        // it will form singleton
        int res = dp[n];
 
        // return the stored value
        // if the value is already computed
        if (res != -1)
            return res;
 
        // base case
        if (n == 1) {
            return res = 1;
        }
 
        // if there are just 2 numbers left,
        // they will form a pair
        if (n == 2) {
            return res = 2;
        }
        else {
            return res = ways(n - 1) + ways(n - 2);
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 10;
        dp = new int[n + 1];
        Arrays.fill(dp, -1);
        System.out.println("Number of ways = " + ways(n));
    }
}
 
// This code is contributed by jainlovely450

Python3

# Python3 implementation of the above approach 
 
# vector to store the computed values
dp=[]
 
# Function to count the number of ways
def ways(n):
    # If there is a single number left 
    # it will form singleton
    res = dp[n]
     
    # return the stored value
    # if the value is already computed
    if(res!=-1):
        return res
 
    # base case
    if (n == 1) :
        res=1
        return res
     
   
    # if there are just 2 numbers left, 
    # they will form a pair
    if (n == 2) :
        res=2
        return res
     
    else :          
        res = ways(n - 1) + ways(n - 2)
        return res
     
 
 
# Driver Code
if __name__ == '__main__':
    n = 5
    dp = [-1]*(n + 1)
    print("Number of ways =",ways(n))

C#

using System;
 
class Program {
    // vector to store the computed values
    static int[] dp;
 
    // Function to count the number of ways
    static int Ways(int n) {
        // If there is a single number left
        // it will form singleton
        int res = dp[n];
 
        // return the stored value
        // if the value is already computed
        if(res!=-1) {
            return res;
        }
 
        // base case
        if (n == 1) {
            res=1;
            return res;
        }
 
        // if there are just 2 numbers left,
        // they will form a pair
        if (n == 2) {
            res=2;
            return res;
        } else {
            res = Ways(n - 1) + Ways(n - 2);
            return res;
        }
    }
    // Derive code
    static void Main(string[] args) {
        int n = 5;
        dp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            dp[i] = -1;
        }
        Console.WriteLine("Number of ways = " + Ways(n));
    }
}
 
 
// This code is contributed by shiv1o43g

Javascript

<script>
// JavaScript implementation of the above approach 
 
// array to store the computed values
let dp = [];
 
// Function to count the number of ways
function ways(n)
{
    // If there is a single number left 
    // it will form singleton
     
      let res = dp[n];
       
      // return the stored value
      // if the value is already computed
      if(res!=-1)
          return res;
   
      // base case
      if (n == 1) {
         res = 1;
         return res;
      }
   
    // if there are just 2 numbers left, 
    // they will form a pair
      if (n == 2) {
        res = 2;
      }
      else {  
        res = ways(n - 1) + ways(n - 2);
      }
 
      dp[n] = res;
      return res;
}
 
// Driver Code
let n = 5;
dp = new Array(n+1).fill(-1);
document.write(dp);
document.write("Number of ways = " + ways(n));
 
// This code is contributed by shinjanpatra
</script>

Output

Number of ways = 8

Time Complexity: O(n)

Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!