Recursion-6

Q1 - Count all the possible paths on an m x n grid from top left (grid[0][0]) to bottom right (grid[m-1][n-1]) having constraints that from each cell you can either move only to right or down. (Easy)
Input m = 2, n = 3
Expected Output 3

import java.util.*;
import java.util.Scanner;
public class Test{
        static int level = -1;
        public static void main(String[] args){
                Scanner scn = new Scanner(System.in);
                System.out.println("Enter the dimensions of the matrix: ");
                int m = scn.nextInt();
                int n = scn.nextInt();
                int sum = 0;
                int i = 0;
                int j = 0;
               System.out.println(NumberOfPaths(m , n , i , j));
        }
        public static int NumberOfPaths(int m , int n , int i , int j){
                if(i >= m || j >= n)
                        return 0;
                if(i == m - 1 && j == n - 1)
                        return 1;
 
                return NumberOfPaths(m , n , i + 1 , j) + NumberOfPaths(m , n , i , j + 1);
        }
}

Q2 - Given an array of integers, print a sum triangle from it such that the first level(the bottom
level in triangular fashion) has all array elements. From then, at each level, the number of
elements is one less than the previous level and elements at the level is the sum of
consecutive two elements in the previous level.

(Medium)

Input1  n = 5
arr = {1, 2, 3, 4, 5}
Output1  [48]
[20, 28]
[8, 12, 16]
[3, 5, 7, 9]
[1, 2, 3, 4, 5]

     
import java.util.*;
import java.util.Scanner;
public class Test{
        static int level = -1;
        public static void main(String[] args){
                Scanner scn = new Scanner(System.in);
                System.out.println("Enter the length of array: ");
                int n = scn.nextInt();
                int[] arr = new int[n];
                System.out.println("Enter the elements of array: ");
                for(int i = 0; i < n; i++){
                        arr[i] = scn.nextInt();
                }
                printTriangle(arr);
        }
        public static void printTriangle(int[] arr) {
                if (arr.length < 1)
                        return;
                // Creating new array which contains the sum of consecutive elements in the array passes as parameter.
                int[] temp = new int[arr.length - 1];
                for (int i = 0; i < arr.length - 1; i++) {
                        int x = arr[i] + arr[i + 1];
                        temp[i] = x;
                }
                // Make a recursive call and pass the newly created array
                printTriangle(temp);
                // Print current array in the end so that smaller arrays are printed first
                System.out.println(Arrays.toString(arr));
        }
}

Q3 - Given an array of size n, generate and print all possible combinations of r elements in array. (Hard)
Input}
n = 4
{1, 2, 3, 4}
r = 2
Expected Output}
{1, 2}
{1, 3}
{1, 4}
{2, 3}
{2, 4}
{3, 4}

import java.util.*;
import java.util.Scanner;
public class Test{
        static int level = -1;
        public static void main(String[] args){
                Scanner scn = new Scanner(System.in);
                System.out.println("Enter the length of array: ");
                int n = scn.nextInt();
                int[] arr = new int[n];
                System.out.println("Enter the elements of array: ");
                for(int i = 0; i < n; i++){
                        arr[i] = scn.nextInt();
                }
                System.out.println("Enter r: ");
                int r = scn.nextInt();
                printCombination(arr, n, r);
        }
        public static void printCombination(int[] arr, int n, int r) {
                // A temporary array to store all combination one by one
                int data[]=new int[r];
                // Print all combination using temporary array 'data[]'
                combination(arr, n, r, 0, data, 0);
        }
        public static void combination(int[] arr, int n, int r, int index, int[] data, int i) {
                // Current combination is ready to be printed, print it
                if (index == r) {
                        for (int j=0; j<r; j++)
                                System.out.print(data[j]+" ");
                        System.out.println("");
                        return;
                }
                // When no more elements are there to put in data[]
                if (i >= n)
                        return;
                // current is included, put next at next location
                data[index] = arr[i];
                combination(arr, n, r, index+1, data, i+1);
                // current is excluded, replace it with next (Note that i+1 is passed, but index is not changed)
                combination(arr, n, r, index, data, i+1);
        }
}

Q4 - Given two sorted arrays A and B of length m and n respectively, generate all possible arrays
such that the first element is taken from A then from B then from A, and so on in increasing order
till the arrays are exhausted. The generated arrays should end with an element from B.

(Hard)

Input:
m = 3
n = 4
A = {10, 15, 25}
B = {1, 5, 20, 30}
Expected Output:
10 20
10 20 25 30
10 30
15 20
15 20 25 30
15 30
25 30

import java.util.*;
import java.util.Scanner;
public class Test{
        public static void main(String[] args){
                Scanner scn = new Scanner(System.in);
                System.out.println("Enter the length of both the arrays: ");
                int m = scn.nextInt();
                int n = scn.nextInt();
                int[] A = new int[m];
                int[] B = new int[n];
                System.out.println("Enter the elements of first array: ");
                for(int i = 0; i < m; i++){
                        A[i] = scn.nextInt();
                }
                System.out.println("Enter the elements of second array: ");
                for(int i = 0; i < n; i++){
                        B[i] = scn.nextInt();
                }
                int[] C = new int[m + n];
                generate(A, B, C, 0, 0, m, n, 0, true);
        }
        public static void generate(int[] A, int[] B, int[] C, int i, int j, int m, int n, int len, boolean flag){
                if (flag) {
                        // Include valid element from A
                        // Print output if there is at least one 'B' in output array 'C'
                        if (len != 0) {
                                printArr(C, len + 1);
                        }
                        // Recur for all elements of A after current index
                        for (int k = i; k < m; k++) {
                                if (len == 0) {     //this block works for the very first call to include the first element in the output array
                                        C[len] = A[k];
                                        // don't increment len as B is included
                                        generate(A, B, C, k + 1, j, m, n, len, !flag);
                                }
                                else if (A[k] > C[len]) { // include valid element from A and recur
                                        C[len + 1] = A[k];
                                        generate(A, B, C, k + 1, j, m, n, len + 1, !flag);
                                }
                        }
                }
                else {  //Include valid element from B and recur
                        for (int l = j; l < n; l++) {
                                if (B[l] > C[len]) {
                                        C[len + 1] = B[l];
                                        generate(A, B, C, i, l + 1, m, n, len + 1, !flag);
                                }
                        }
                }
        }
        public static void printArr(int[] arr, int n) {
                for (int i = 0; i < n; i++)
                        System.out.print(arr[i] + " ");
                System.out.println("");
        }
}