Как использовать рекурсию для решения проблемы PlusMinus

Сегодня мы поговорим о том, как использовать рекурсию для решения конкретной проблемы алгоритма.

Недавно я выполнял задание по кодированию в рамках собеседования, и мне задали проблему с алгоритмом, с которой я раньше не сталкивался. Я подумал, что это особенно интересно, и в то время я понятия не имел, как его решить, поэтому сегодня давайте разберем его вместе. Вот в чем проблема:

Have the function PlusMinus(num) read the num parameter being passed which will be a combination of 1 or more single digits, and determine if it's possible to separate the digits with either a plus or minus sign to get the final expression to equal zero. For example: if num is 35132 then it's possible to separate the digits the following way, 3 - 5 + 1 + 3 - 2, and this expression equals zero. Your program should return a string of the signs you used, so for this example your program should return -++-. If it's not possible to get the digit expression to equal zero, return the string not possible.If there are multiple ways to get the final expression to equal zero, choose the one that contains more minus characters. For example: if num is 26712 your program should return -+-- and not +-+-.

Хорошо, в этой задаче много информации, поэтому давайте разберем ее:

Что мы пытаемся сделать?

Я думаю, что в этой задаче это звучит странно, но мы возьмем число, состоящее из одной или нескольких цифр. Сначала нам нужно разделить число до отдельных целых чисел, составляющих число. Затем мы хотим выяснить, можно ли поставить знаки плюса или минуса между числами в некоторой комбинации, чтобы все это равнялось нулю. Наконец, мы возвращаем этот список плюсов и минусов или возвращаем «невозможно», если эти числа не могут равняться нулю в любой комбинации.

Итак, с чего мы начнем?

После того, как мы убедимся, что понимаем проблему, следующим шагом будет разобраться в некоторых примерах. В задаче есть хороший вариант, поэтому давайте воспользуемся им, и я также добавил один, который дает нам «невозможный» результат:

let num = 35132
//expected output: '-++-'

let anotherNum = 199
//expected output: 'not possible'

Давайте составим план:

Во-первых, нам нужно найти способ привести наши данные в правильную форму. Нам дано целое число, поэтому нам нужно разбить это целое число на отдельные числа.
Давайте создадим массив для хранения строк возможных решений.
Мы собираемся написать вспомогательную функцию для обхода нашего массива чисел. Вот тут и пригодится наша рекурсия.
Мы собираемся написать еще одну вспомогательную функцию, чтобы найти наилучшее возможное решение из тех, которые мы придумали.
Затем возвращаем возможность с наибольшим количеством минусов или возвращаем «невозможно»

Я знаю, что я немного не обращал внимания на вышеприведенные пикантные подробности, я буду разбирать их под каждым фрагментом кода.

function PlusMinus(num) {
    let array = String(num).split('').map((num) => parseInt(num));
    const possibilities = []

Приведите целое число в правильную форму

Нам нужно, чтобы это целое число было разбито на отдельные числа, из которых оно состоит, поэтому я хочу разбить его на массив. Я могу сделать это с помощью метода split, но сначала мне нужно преобразовать целое число в строку.

Сделайте num строкой. Как? Я использую его как функцию для преобразования типов, вы можете найти его под заголовком Конструктор здесь.
Используйте метод split для строки, это превратит ее в массив строк, содержащий строковую версию каждого из наших чисел.
Отобразите наш новый массив строк и снова превратите каждую из них в числа с помощью parseInt. Если вы не знакомы с parseInt, посмотрите документацию.
Создайте массив для хранения наших списков возможных комбинаций знаков, которые мы собираемся составить на следующем шаге.

Пора написать нашу рекурсивную вспомогательную функцию

Теперь мы переходим к сути этой проблемы: как написать рекурсивную часть нашего решения. Пояснение ниже:

const traverse = ([currNum, ...otherNums], combination, sum) => {
  if (otherNums.length === 0) {
    if (sum + currNum === 0) possibilities.push(combination + '+');
    if (sum - currNum === 0) possibilities.push(combination + '-');
    } else {
       traverse(otherNums, combination + '+', sum + currNum);
       traverse(otherNums, combination + '-', sum - currNum);
    }
  };

Наша функция примет часть нашего исходного массива. То, что я делаю в первой строке, - это деструктуризация этой части массива, чтобы я мог получить доступ к различным его частям с переменными, которые я объявляю. В этом случае currNum теперь относится к первому числу этого массива, а otherNums теперь относится к остальным числам в этом массиве.
В нашем базовом случае мы проверяем, есть ли еще какие-нибудь числа, кроме того, которое мы назвали currNum. Если их нет, то это означает, что мы получили массив из одного числа, и мы можем вставить комбинацию знаков «+» и «-», которые мы создали при вызове этих функций в наш массив возможностей. Зачем нам нужен массив возможностей? Нам нужен массив возможностей, чтобы в самом конце мы могли проверить, какая из возможных комбинаций знаков имеет больше всего знаков «-», и это будет та, которую мы вернем.
Если мы еще не достигли точки наличия только одного элемента массива, мы снова вызываем нашу функцию обхода, один раз для плюсовой возможности и один раз для минусовой возможности. Я настоятельно рекомендую использовать такой сайт, как AlgoViz, чтобы действительно понять порядок, в котором функции помещаются в стек вызовов. Просто скопируйте код из нижней части этой статьи в редактор кода на AlgoViz и посмотрите, как он запустится. Помните, что первый вызов функции, который мы выполняем, будет добавлен в стек вызовов, и после него ничего не будет выполняться до тех пор, пока он не будет разрешен.

Давайте напишем вспомогательную функцию, чтобы выяснить, у какой возможности больше всего минусовых знаков.

const mostMinus = (possibilitiesArray) => {
    return possibilitiesArray.reduce((acc, curr) =>
       [...acc].filter((sign) => sign === '-').length >  
       [...curr].filter((sign) => sign === '-').length ? acc : curr );
};

Мы передаем массив возможных комбинаций знаков, который на данный момент должен быть массивом строк, содержащих комбинацию знаков плюс и минус, которые потребовались для получения наших результатов. Этот массив был построен, когда мы достигли последнего шага нашей функции обхода выше, когда мы поместили нашу комбинацию в массив.
Мы будем использовать метод уменьшения массива для нашего массива возможностей, чтобы уменьшить этот массив до возможности с наибольшим минусом. Он вернет строку. Если мы посмотрим на документацию для сокращения, мы увидим, что если мы не передадим начальное значение для аккумулятора, он просто будет использовать наше первое значение в массиве, которое мы хотим для нашей текущей цели.
Мы распределяем наш аккумулятор в массив, а затем фильтруем его, используя условие, что знак является «-». Аккумулятор в этот момент - это всего лишь первая строка плюсов и минусов, которая была в нашем массиве, потому что мы не передали начальное значение аккумулятору.
Мы распределяем наш текущий элемент в массив, а также фильтруем его, используя условие знака «-».
Мы сравниваем два, чтобы увидеть, какой из них больше, т. Е. На котором больше знаков минус. Здесь мы используем тернарный оператор, если вы не знакомы с ним, найдите его, он может быть действительно полезен.
Если в аккумуляторе больше знаков «минус», мы возвращаем его, в противном случае мы возвращаем текущую строку, которую мы ищем. В любом случае наш массив возможностей теперь сокращен до одной строки, содержащей наибольшее количество знаков минус.

Напишите инструкцию для использования вспомогательных функций, которые мы написали выше

До сих пор мы фактически ничего не сделали, чтобы найти решение. Мы написали только вспомогательные функции, которые еще не вызывали. Пришло время вызвать наши функции и вернуть результат:

    traverse(array.slice(1), '', array[0]);
    return possibilities.length ? 
    mostMinus(possibilities) : 'not possible';
}

Теперь мы вызываем нашу функцию обхода, которую мы уже написали. Мы передадим в качестве первого аргумента срез нашего массива от первого индекса до конца. Это потому, что мы будем использовать первое значение в качестве начальной суммы. Мы передаем пустую строку, которая будет нашим начальным значением для комбинации, и мы передаем первый элемент нашего массива (тот, который мы отрезали) как наше начальное значение для суммы.
Для нашего оператора return мы видим, есть ли какие-либо строки в нашем массиве возможностей, если они есть, мы вызываем нашу функцию mostMinus в массиве, а если нет, мы возвращаем строку 'not possible', потому что у нас не было никаких возможных комбинаций «+» или «-», чтобы наши числа равнялись нулю.

Вот полный код

В этой проблеме предстоит многое сделать, но над ней интересно работать. Он также использует множество действительно полезных методов массива, которые вам следует знать. Если вы не поищете их и не прочтете документацию. Я действительно рекомендую выяснить, что делает стек вызовов, когда вы проходите через раздел рекурсии. Если вы заблудились, как это делал я несколько раз, решая эту проблему, если у вас остались вопросы или вы просто хотите подключиться, свяжитесь со мной в LinkedIn. Если у вас есть более оптимизированное или итеративное решение этой проблемы, дайте мне знать!

Как использовать рекурсию для решения проблемы PlusMinus