Intuition
We always need to analyze the problem carefully and obtain the key points mentioned in the statement. From given conditions, we can observe that bracket sequences and operators can be inserted anywhere, which will result in many outcomes, out of which, one could be 28. This observation leads us to use a backtracking algorithm.
Approach
In order to solve this problem with a backtracking algorithm, we need to implement three functions to resolve four elements of the given array NUMS[] and reach an outcome.
- First function checkResolve_4(int num1, int num2, int num3, int num4), will take the complete array NUMS[] as an argument and will try applying all four operations between every consecutive element and call the following function recursively, checkResolve_3().
- The second function, checkResolve_3(double num1, double num2, double num3), will take three double values as arguments because the division operator can generate double values. Then it will check if we can generate 28 by applying given operations on all consecutive elements and call the further function checkResolve_2().
- The final function checkResolve_2(double num1, double num2) will take the final two elements as arguments and return whether any of the four operations between these two values can generate 28.
- While comparing the final result with 28 in the function checkResolve_2(), we need to introduce a tolerance value to manage issues related to precision.
Program
// Program to find if 28 can be generated.
#include <iostream>
#include <vector>
using namespace std;
// Function to resolve the final two elements to generate one outcome.
bool checkResolve_2(double num1, double num2)
{
// Variable to store tolerance in precision.
double tolerance = 0.001;
// Addition operation on final elements.
if (abs(num1 + num2 - 28.0) <= tolerance)
return true;
// Subtraction operation on final elements.
if (abs(num1 - num2 - 28.0) <= tolerance)
return true;
// Multiplication operation on final elements.
if (abs(num1 * num2 - 28.0) <= tolerance)
return true;
// Division operation on final elements.
if (num2 != 0 && abs(num1 / num2 - 28.0) <= tolerance)
return true;
// Return false if 28 is not generated with all four operations.
return false;
}
// Function to resolve three elements to generate one outcome.
bool checkResolve_3(double num1, double num2, double num3)
{
// Variable to store the result.
bool possible = false;
// Applying all four operations on the first two consecutive elements.
if(!possible)
possible = possible | checkResolve_2(num1 + num2, num3);
if(!possible)
possible = possible | checkResolve_2(num1 - num2, num3);
if(!possible)
possible = possible | checkResolve_2(num1 * num2, num3);
if(!possible && num2 != 0)
possible = possible | checkResolve_2(num1 / num2, num3);
// Checking if 28 is possible with operations on the first two consecutive elements.
if (possible)
return true;
// Applying all four operations on the second two consecutive elements.
if(!possible)
possible = possible | checkResolve_2(num1, num2 + num3);
if(!possible)
possible = possible | checkResolve_2(num1, num2 - num3);
if(!possible)
possible = possible | checkResolve_2(num1, num2 * num3);
if(!possible && num3 != 0)
possible = possible | checkResolve_2(num1, num2 / num3);
// Returning the final verdict.
return possible;
}
// Function to resolve four elements to generate one outcome.
bool checkResolve_4(int num1, int num2, int num3, int num4)
{
// Variable to store the result.
bool possible = false;
// Applying all four operations on the first two consecutive elements.
if(!possible)
possible = possible | checkResolve_3(num1 + num2, num3, num4);
if(!possible)
possible = possible | checkResolve_3(num1 - num2, num3, num4);
if(!possible)
possible = possible | checkResolve_3(num1 * num2, num3, num4);
if(!possible && num2 != 0)
possible = possible | checkResolve_3(num1 / num2, num3, num4);
// Checking if 28 is possible with operations on the first two consecutive elements.
if (possible)
return true;
// Applying all four operations on the second two consecutive elements.
if(!possible)
possible = possible | checkResolve_3(num1, num2 + num3, num4);
if(!possible)
possible = possible | checkResolve_3(num1, num2 - num3, num4);
if(!possible)
possible = possible | checkResolve_3(num1, num2 * num3, num4);
if(!possible && num3 != 0)
possible = possible | checkResolve_3(num1, num2 / num3, num4);
// Checking if 28 is possible with operations on the second two consecutive elements.
if (possible)
return true;
// Applying all four operations on the last two consecutive elements.
if(!possible)
possible = possible | checkResolve_3(num1, num2, num3 + num4);
if(!possible)
possible = possible | checkResolve_3(num1, num2, num3 - num4);
if(!possible)
possible = possible | checkResolve_3(num1, num2, num3 * num4);
if(!possible && num4 != 0)
possible = possible | checkResolve_3(num1, num2, num3 / num4);
// Returning the final verdict.
return possible;
}
// Main Function.
int main()
{
// Vector to store the four elements.
vector<int> NUMS(4);
// Input of vector.
for (int i = 0; i < 4; i++)
cin >> NUMS[i];
// Printing the output.
if (checkResolve_4(NUMS[0], NUMS[1], NUMS[2], NUMS[3]))
cout << "28 can be generated";
else
cout << "NO";
return 0;
}

You can also try this code with Online C++ Compiler
Run Code
Example
Input:
1 14 4 2
Output:
28 can be generated
Complexity Analysis
Time Complexity: O(43 x 3!)
Explanation: Complexity generated by all three functions:
(4 x 3) x (4 x 2) x (4 x 1) = 43 x 3!
Space Complexity: O(1)
Explanation: No extra space has been used
Key Takeaways
In this article, we’ve discussed the “Arrange elements of the given array in a mathematical expression using operators [+, -, *, /] and parentheses to get value 28” problem. Here an effective method has been used, which is called backtracking. It also involves arithmetic concepts like BODMAS which enhances one’s mathematical skills. More such problems can be found on Backtracking Problems. These questions are asked during various coding contests as well as placements tests.
Check out this article - Balanced Parentheses
If you want to learn more before jumping into practicing, head over to our library section for many such interesting blogs. Keep learning.
Happy Coding!