Ciąg znaków posiada 10 elementów. Pomiędzy nimi może wystąpić maksymalnie 9 połączeń tak, aby utworzyły jakaś liczbę. Możesz zadeklarować 9-elementową tablicę, której wartości będą przedstawiać rodzaj połączenia:
- 0 dla {8, 9} -> 89
- 1 dla {8, 9} -> 8 + 9
- 2 dla {8, 9} -> 8 - 9
Dla połączeń | 0 1 0 1 0 0 2 0 0 | otrzymamy: 12+34+567-890
Teraz wygenerujmy wszystkie możliwe kombinacje z powtórzeniami:
bool next_combination(std::vector<int>& vec, int max) {
for (auto& value : vec) {
if (++value <= max) {
return true;
}
value = 0;
}
return false;
}
Przykład wypisania wszystkich możliwych ciągów do przeliczenia:
#include <iostream>
#include <string>
#include <vector>
bool next_combination(std::vector<int>& vec, int max) {
for (auto& value : vec) {
if (++value <= max) {
return true;
}
value = 0;
}
return false;
}
void print_vec(std::vector<int> const& ints) {
std::cout << "| ";
for (auto i : ints)
std::cout << i << " ";
std::cout << " |\n";
}
void print_expr(std::string const& pattern, std::vector<int> const& connections) {
std::cout << pattern.front();
for (std::size_t i = 0; i < connections.size(); ++i) {
if (connections[i] != 0) {
std::cout << (connections[i] == 1 ? '+' : '-');
}
std::cout << pattern[i + 1];
}
std::cout << "\n";
}
int main() {
std::string pattern = "1234567890"; // std::vector<int>
std::vector<int> connections(pattern.size() - 1);
do {
print_expr(pattern, connections);
print_vec(connections);
} while (next_combination(connections, 2));
}
Następnie oblicz wszystkich powstałe wyrażenia i porównuj wyniki z liczbą podaną na wejściu.
