Brute-force algorithm for finding a valid equation for a given string of numbers

findEq.js

/*
  The first 12 digits of pi are 314159265358. We can make these digits into an
  expression evaluating to 27182 (first 5 digits of e) as follows:

  3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182
  or
  3 + 1 - 415 * 92 + 65358 = 27182

  Notice that the order of the input digits is not changed. Operators (+,-,/,
  or *) are simply inserted to create the expression.

  Write a function to take a list of numbers and a target, and return all the
  ways that those numbers can be formed into expressions evaluating to the
  target

  For example:
  f("314159265358", 27182) should print:

  3 + 1 - 415 * 92 + 65358 = 27182
  3 * 1 + 4 * 159 + 26535 + 8 = 27182
  3 / 1 + 4 * 159 + 26535 + 8 = 27182
  3 * 14 * 15 + 9 + 26535 + 8 = 27182
  3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182

  ------------------------------------------------------------------------------
*/

/*
    Sample input: 123456
    Result        Set size
    ----------------------
    1 2 3 4 5 6   1
    12 34 56      2
    123 456       3
    1234 56       4
    12 3456       4 <-- Notice how this groups in reverse
    12345 6       5
    1 23456       5 <-- Notice how this groups in reverse
    123456        6
 */
/**
 * Cuts the string into every permutation
 * @param  {String} str String to cut
 * @return {Array}     Array of all combinations of 'cuts'
 */
const cutString = (str) => {
  const returnArr = [];

  // Foward
  for (let setSz = 1; setSz < str.length; setSz++) { // Set size
    const arr = [];
    let charIndex = 0;
    while (charIndex < str.length) {
      arr.push(str.substr(charIndex, setSz));
      charIndex += setSz;
    }
    returnArr.push(arr);
  }

  // Backwards
  // Reverse input string
  const reversed = str.split('').reverse().join(''); // hacky reversal of string

  for (let setSz = 1; setSz < str.length; setSz++) { // Set size
    const arr = [];
    let charIndex = 0;
    while (charIndex < str.length) {
      const unreverse = reversed.substr(charIndex, setSz).split('').reverse().join('');
      arr.push(unreverse);
      charIndex += setSz;
    }
    // Only add if it doesn't exist already
    if (returnArr.findIndex(x => x.sort().toString() === arr.sort().toString()) === -1) {
      returnArr.push(arr);
    }
  }
  return returnArr;
};

/**
 * Given an array of strings, generates a string of length k containing all
 * possible combinations of the input strings
 * @param  {Array} a Array of strings to pick from
 * @param  {Integer} k   length of the resultant string
 * @return {Array}     Returns an array of arrays of input strings
 */
const generateForK = (a, k) => {
  const result = [];
  const _generate = (arr, prefix, n, j) => {
    // Base case: k is 0, print prefix
    if (k === 0) {
      result.push(prefix);
      return;
    }
    // One by one add all characters from set and recursively call for k equals to k-1
    for (let i = 0; i < n; i++) {
      // Next character of input added
      const newPrefix = [...prefix, arr[i]];
      // k is decreased, because we have added a new character
      _generate(arr, newPrefix, n, j - 1);
    }
  };
  _generate(a, [], a.length, k);
  return result;
};
// console.log('generate', generateForK([' + ',' - ',' * '], 3));

/**
 * Given an array of operands, return an array of equations containing all
 * combinations of possible operators on the operands
 * @param  {Array} operandSet Array of operands
 * @return {Array}            Array of equations
 */
const applyOperator = (operandSet) => {
  const eqs = [];
  const ops = [' + ', ' - ', ' * ', ' / '];

  for (const operands of operandSet) {
    const operatorSet = generateForK(ops, operands.length - 1);
    for (const operators of operatorSet) {
      let output = '';
      for (let i = 0; i < operands.length; i++) {
        output += `${operands[i]}`;
        if (i < operands.length - 1) {
          output += `${operators[i]}`;
        }
      }
      eqs.push(output);
    }
  }
  return eqs;
};
// console.log('apply op', applyOperator([[1,23]])); // yields [12+24, 12-34, 12*34, 12/34]

/**
 * Glue function that brings all of the above together to find the valid
 * solutions for a string
 * @param  {String} input  Input string of numbers to select from
 * @param  {Integer} target Target number
 */
const findEqs = (input, target) => {
  const inputPerms = cutString(input);
  const eqs = applyOperator(inputPerms);
  const solutions = [];
  for (const eq of eqs) {
    if (eval(eq) === target) {
      solutions.push(eq);
    }
  }
  if (solutions.length === 0) {
    console.log(`No solutions found for ${input}, ${target}`);
  }
  else {
    console.log(`${solutions.length} solution${solutions.length === 1 ? '' : 's'} found for ${input}, ${target}:`);
  }
  for (const soln of solutions) {
    console.log(`${soln} = ${target}`);
  }
};

findEqs('232', 12);
findEqs('323', 3);
findEqs('3232', 15);
findEqs('19238', 13);

// Can you come up with a better solution?

This solution uses an ES6 generator and can solve for the first 12 digits of Pi.
https://github.com/monte-hayward/equation-maker-js

How's this?

const appendToFormula = (f, op, digit) => `${(f.match(/[-+].$/) && !op.match(/[-+]/) ? `(${f})` : `${f}`)}${op}${digit}`;

const genFormulas = (s, tv, f = "", cv = 0) => {
  let rc = []
  if (!s) {
    if (cv === tv) {
      rc = [ f ];
    }
  } else {
    const digit = s.substring(0, 1);
    const rest = s.substring(1);

    const dval = parseInt(digit);

    if (!f) {
      rc = genFormulas(rest, tv, digit, dval);
    } else {
      const plus = genFormulas(rest, tv, appendToFormula(f, '+', digit), cv+dval);
      const minus = genFormulas(rest, tv, appendToFormula(f, '-', digit),  cv-dval);
      const multiply = genFormulas(rest, tv, appendToFormula(f, '*', digit),  cv*dval);
      let divide = [];
      if (dval && !(cv % dval)) {
        divide = genFormulas(rest, tv, appendToFormula(f, '/', digit), cv/dval);
      }

      rc = [ ...plus, ...minus, ...multiply, ...divide ];
    }
  }

  return rc;
};