Учитывая массив цифр 0-9 и целое число n, найдите все целые числа, которые могут быть сформированы из входного массива и меньше чем n

Question

Вот проблема:

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

Например, если заданы в качестве входов [2, 5, 8] и n = 223, то следующим выводом должно быть:

[2, 5, 8, 22, 25, 28, 52, 55, 58, 82, 85, 88, 222]

Очевидно, что любое целое число с меньшим количеством цифр, чем n будет принято, а любое с большим количеством отклоненных. Но как наиболее эффективно найти те, которые имеют одинаковое количество цифр? Решение, которое я знаю, состояло бы в том, чтобы иметь вложенные циклы, по одной на каждую цифру во входном целом числе, и формировать каждую возможную комбинацию цифр из входного массива и проверять ее. против n . Хотя это кажется неуклюжим, и мне интересно, есть ли лучший способ.

Answer 1

Использовать рекурсию.

Напишите функцию, которая выводит все ответы с тем же количеством цифр, что и n. Вызовите эту функцию doit(n). Затем псевдокод для него:

1. Найдите самую значимую цифру n, назовите ее d
2. Для всех цифр d1, меньших d, вывести все числа, начинающиеся с d1
3. Удалить цифру d из n; назвать результат n1
4. Звоните doit(n1); к каждому номеру в результирующем списке добавьте цифру d