Given an integer N, the task is to print all the possible arithmetic expressions using all numbers from 1 to N and with binary operator +, –, * and /.
Examples:
Input: n = 2
Output:
1+2, 1-2, 1/2, 1*2
Input: n = 3
Output:
1+2+3, 1+2-3, 1+2/3, 1+2*3, 1-2+3, 1-2-3, 1-2/3, 1-2*3
1/2+3, 1/2-3, 1/2/3, 1/2*3, 1*2+3, 1*2-3, 1*2/3, 1*2*3
Approach:
- We will create a character array of length = n + n – 1, because for an expression with n operands to be valid we will need n-1 operators.
- Iterate the array and put numbers at even position whereas symbols at the odd position and call the function recursively.
- If number of characters becomes equal to the length of array, print the array.
Below is the implementation of the above approach:
CPP
// C++ program to print all the // expressions for the input value #include<iostream>#include<bits/stdc++.h>using namespace std;// Function to print all the// expressions using the numbervoid PrintRecursive(char *str,int arr[], int i, int n,char *res, int j, int len,int ln){ // Termination condition if(j==len) { res[j]='\0'; cout<<res<<endl; return; } // Even position will contain // the numbers if(j%2==0) { res[j]='0'+arr[i]; // Recursive call PrintRecursive(str,arr,i+1,n,res, j+1,len,ln); } else { // Add a symbol from string in // odd position. for(int k=0;k<ln;k++) { res[j]=str[k]; PrintRecursive(str,arr,i,n,res, j+1,len,ln); } }}void PrintExpressions(int n){ // Character array containing // expressions char str[4]={'+','-','/','*'}; str[4]='\0'; int ln=strlen(str); int a[n]; for(int i=0;i<n;i++) { a[i] = i + 1; } char res[( 2 * n ) - 1]; PrintRecursive(str,a,0,n,res,0, 2*n-1,ln); return;}//Driver codeint main(){ int n = 2; PrintExpressions(n); return 0;} |
Java
/*package whatever //do not write package name here */import java.util.*;class GFG { // Function to print all the // expressions using the number static void PrintRecursive(char []str,int arr[], int i, int n,char []res, int j, int len,int ln) { // Termination condition if(j == len) { System.out.println(res); return; } // Even position will contain // the numbers if(j%2==0) { res[j]=(char)('0'+arr[i]); // Recursive call PrintRecursive(str,arr,i+1,n,res,j+1,len,ln); } else { // Add a symbol from string in // odd position. for(int k=0;k<ln;k++) { res[j]=str[k]; PrintRecursive(str,arr,i,n,res,j+1,len,ln); } } } static void PrintExpressions(int n) { // Character array containing // expressions char str[] = {'+','-','/','*'}; int ln=str.length; int a[] = new int[n]; for(int i=0;i<n;i++) { a[i] = i + 1; } char res[] = new char[( 2 * n ) - 1]; PrintRecursive(str,a,0,n,res,0,2*n-1,ln); } public static void main (String[] args) { int n = 2; PrintExpressions(n); }}// This code is contributed by aadityaburujwale. |
Python3
# Python3 program to print all the # expressions for the input value # Function to print all the# expressions using the numberdef PrintRecursive(str, arr, i, n, res, j, len, ln): # Termination condition if(j==len): print(res) return # Even position will contain # the numbers if(j%2==0): res[j] = arr[i] # Recursive call PrintRecursive(str,arr,i+1,n,res,j+1,len,ln) else: # Add a symbol from string in # odd position. for k in range(0,ln): res[j] = str[k] PrintRecursive(str,arr,i,n,res,j+1,len,ln)def PrintExpressions(n): # Character array containing # expressions str = [ '+','-','/','*' ] ln = len(str) a = [] for i in range(0,n): a.append(0) a[i] = i + 1 res = [] for i in range(0,(2 * n)-1): res.append('') PrintRecursive(str, a, 0, n, res, 0, 2*n-1, ln) return# Driver coden = 2PrintExpressions(n)# This code is contributed by akashish__ |
C#
using System;using System.Collections.Generic;public class GFG { // Function to print all the // expressions using the number public static void PrintRecursive(char[] str, int[] arr, int i, int n, char[] res, int j, int len, int ln) { // Termination condition if (j == len) { Console.WriteLine(res); return; } // Even position will contain // the numbers if (j % 2 == 0) { string temp = arr[i].ToString(); res[j] = temp[0]; // Recursive call PrintRecursive(str, arr, i + 1, n, res, j + 1, len, ln); } else { // Add a symbol from string in // odd position. for (int k = 0; k < ln; k++) { res[j] = str[k]; PrintRecursive(str, arr, i, n, res, j + 1, len, ln); } } } public static void PrintExpressions(int n) { // Character array containing // expressions char[] str = new char[4] { '+', '-', '/', '*' }; int ln = str.Length; int[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = i + 1; } char[] res = new char[(2 * n) - 1]; PrintRecursive(str, a, 0, n, res, 0, 2 * n - 1, ln); return; } static public void Main() { int n = 2; PrintExpressions(n); }}// This code is contributed by akashish__ |
Javascript
// JS program to print all the // expressions for the input value // Function to print all the// expressions using the numberfunction PrintRecursive(str, arr, i, n, res, j, len, ln){ // Termination condition if(j==len) { res[j]; console.log(res); return; } // Even position will contain // the numbers if(j%2==0) { res[j] = arr[i].toString(); // Recursive call PrintRecursive(str,arr,i+1,n,res,j+1,len,ln); } else { // Add a symbol from string in // odd position. for(let k = 0; k < ln; k++) { res[j] = str[k]; PrintRecursive(str,arr,i,n,res,j+1,len,ln); } }}function PrintExpressions(n){ // Character array containing // expressions let str = [ '+','-','/','*' ]; let ln=str.length; let a = []; for(let i = 0; i < n; i++) { a.push(0); a[i] = i + 1; } let res = []; for(let i = 0; i < ( 2 * n ) - 1; i++) { res.push(''); } PrintRecursive(str, a, 0, n, res, 0, 2*n-1, ln); return;}// Driver codelet n = 2;PrintExpressions(n);// This code is contributed by akashish__ |
Output:
1+2 1-2 1/2 1*2
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
