Все возможные комбинации (с повторением) в виде значений в массиве с использованием рекурсии

Я пытаюсь решить проблему, в которой мне нужно вставить математические операции (в данном случае +/-) между цифрами или объединить их, чтобы получить запрошенный номер.

Например: 123456789 => 123+4-5+6-7+8-9 = 120

Моя концепция заключается в генерации различных комбинаций кодов операций в массиве и вычислении выражения до тех пор, пока оно не станет равным некоторому числу.

Проблема в том, что я не могу придумать способ генерировать каждую возможную комбинацию математических операций с использованием рекурсии.

Вот код:

#include <iostream>
#include <algorithm>

using namespace std;

enum {noop,opplus,opminus};//opcodes: 0,1,2

int applyOp(int opcode,int x, int y);
int calculate(int *digits,int *opcodes, int length);
void nextCombination();

int main()
{
int digits[9] = {1,2,3,4,5,6,7,8,9};
int wantedNumber = 100;

int length = sizeof(digits)/sizeof(digits[0]);

int opcodes[length-1];//math symbols
fill_n(opcodes,length-1,0);//init

while(calculate(digits,opcodes,length) != wantedNumber)
{
//recursive combination function here
}

return 0;
}
int applyOp(int opcode,int x, int y)
{
int result = x;
switch(opcode)
{
case noop://merge 2 digits together
result = x*10 + y;
break;
case opminus:
result -= y;
break;
case opplus:
default:
result += y;
break;
}
return result;
}
int calculate(int *digits,int *opcodes, int length)
{
int result = digits[0];
for(int i = 0;i < length-1; ++i)//elem count
{
result = applyOp(opcodes[i],result,digits[i+1]);//left to right, no priority
}
return result;
}

0

Решение

Ключ возвращается. Каждый уровень ручки рекурсии
одна цифра; кроме того, вы захотите остановить рекурсию
тот, который вы закончили.

Самый простой способ сделать это — определить Solver класс, который
отслеживает глобальную информацию, например, сгенерированную строку
пока и промежуточный итог, и сделать рекурсивную функцию
член. В основном что-то вроде:

class Solver
{
std::string const input;
int const target;

std::string solution;
int total;
bool isSolved;

void doSolve( std::string::const_iterator pos );
public:
Solver( std::string const& input, int target )
: input( input )
, target( target )
{
}

std::string solve()
{
total = 0;
isSolved = false;
doSolve( input.begin() );
return isSolved
? solution
: "no solution found";
}
};

В doSolve, вы должны сначала проверить, закончили ли вы
(pos == input.end()): если так, установите isSolved = total == target
и немедленно возвращайтесь; в противном случае, попробуйте три варианта,
(total = 10 * total + toDigit(*pos), total += toDigit(*pos),
а также total -= toDigit(*pos)), каждый раз сохраняя оригинал
total а также solution, добавив необходимый текст в
solutionи звонит doSolve с увеличенным pos,
По возвращении из рекурсивного вызова, если ! isSolved, восстановить
предыдущие значения total а также solutionи попробуйте следующий
возможность. Вернись, как только увидишь isSolvedили когда все
три возможности были решены.

1

Другие решения

Других решений пока нет …