Войти Регистрация
Алгоритмы

150. Слипшиеся суммы в распознанном чеке

Средняя

Приложение распознало фото чека, но потеряло разделители: суммы покупок в рублях слиплись в строку digits. Итог чека total распознан верно.

Расставьте между цифрами знаки + (можно не во все промежутки), чтобы сумма слагаемых была равна total. Слагаемое не начинается с нуля, кроме самого числа 0.

Верните все такие записи вида "120+35+7", отсортированные как строки. Если способов нет — пустой список.

В работе: Разбор чеков в СберБанк Онлайн для учёта расходов: когда распознавание ошиблось, клиенту показывают варианты на выбор.

Пример 1

Ввод
digits = "120357"
total = 162
Вывод
["120+35+7"]

120 + 35 + 7 = 162. Других разбиений с таким итогом нет.

Пример 2

Ввод
digits = "1005"
total = 15
Вывод
["10+0+5"]

`10 + 05` не годится: слагаемое с ведущим нулём. Ответ — `10+0+5`.

Ограничения

  • 1 ≤ длина digits ≤ 12
  • 0 ≤ total ≤ 10¹²
  • Лимит — 2 с на тест (2000 мс).
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def receipt_splits(digits, total):
Перебор с возвратомСтрокиОтсеченияцельпо числу ответов

Источник: наша задача на данных Сбера. Условие пересказано своими словами.