Find expressions equal to a given number using 15 integers with 4 operators

For example, given 15 integers

70, 75, 32, 4, 64, 98, 73, 52, 36, 88, 96, 58, 79, 39, 75

How can we obtain is 72?

4 operators can be used for the 15 integers to get the equation to the answer of 72, which are + - * /. Divison is only allowed where there is no remainder.
A few answers will be

• 4+32+36+39+52-58-64-70+73+75/75-79-88+96+98

• 4+32+36-39-52+5864+70+7375+75+79+88-96*98

• 4+323639/52-58+64-70+7375-7579-88-96-98

• 4+323639/52-98+64-70+7375-7579-88-96-58

Rules

• 5+1-3 and 5-3+1 are 2 different answers.

• No duplicated answer.

• All 15 integers must be used in the equation in any order.

Time given is 200 seconds.

What is the "best" strategy or optimization can be used to obtain as many expressions as possible in the allotted time? The brute-force complexity is (15!*414), which is approximately 3.5 × 1020.

The code below is the code written by me and it is partially optimized by me, it just able to compute 1.0e9 combinations in 200s.
Performance analysis shows that prev_num_pos() used 31% of computation time and
nextoptgroup() used 15% of computation time.

```
#include
#include
#include
#include
using namespace std;

#define PROBLEMSIZE 15
#define PRINTTOSCREEN false
#define OPERATIONUSED 3

int numgroup[PROBLEMSIZE]; //numbers array
int optgroup[PROBLEMSIZE - 1]; //operations array
int theanswer; //the target answer
int size=PROBLEMSIZE;
ofstream output("solution.txt", ios::app);

bool nextoptgroup(){ //true = success next-ed, false = tried all combinations
for (int i = PROBLEMSIZE - 2; i >= 0; i--){ //bruteforce type
if (optgroup[i] = 0; i--){ //used for num position
if (opt[i] != -1) return i + 1;
}
return 0;
}

void debug_print(int num[],int opt[]){
cout > numgroup[i];
}
input >> theanswer; //get answer
input.close();
cout 1){
if (PRINTTOSCREEN) cout << "ERROR FOUND!! CODE:CNUMGROUPSIZEisNOT1\n";
}
el

Another way of looking at it is, rather than rearranging the numbers, just rearrange the symbols. For example, with your fifteen numbers you have 14 symbols between them, with any of 4 values: - + / *

Since each location is independent of each other, you are actually describing a binary number, with 2 bits per symbol location, for a total of 28 bits (=268,435,456)

Looked at it from this point of view, you just count from 0 to 268435456 and use each pair of bits in sequence to determine whether you use a +, -, / or * at that point. Here's some code that does that:

int a[]={4, 32, 36, 39, 52, 58, 64, 70, 73, 75, 75, 79, 88, 96, 98};
int aTot=sizeof(a)/sizeof(a[0]);
long i=0, bitMask=1, sum=0, count=0, limit=268435456;
for (long bits=0;bits>=2;
  }
  if (sum==72)
  {
    bitMask=bits;
    std::cout >=2;
    }
    std::cout << '\n';
  }
}

We massage the bits to get our sum, and if it matches 72, we just repeat the process to print out the formula.

Note the test for division - if the modulo fails, then it won't divide evenly, so we give up and break out of the loop.

Using this, I got 157 answers in about 11 seconds - which gives you another 189 seconds to permute the numbers and run it again (check out next_permutation for how to speed that up). Or you could take those 157 answers and rearrange them, letting you skip some math (and gain some speed).

In any case, hopefully this will give you a starting point to do the calcs...

StackExchange Code Review Q#133101, answer score: 3