algorithm - 给定一个数字数组 0-9 和一个整数 n，找到可以由输入数组组成且小于 n 的所有整数

Question

问题是:

You are given an array of digits 0-9 and an integer n. The array may contain duplicates of any given digit. Find all the integers which can be formed by contatenating digits from the input array and are less than n. Digits from the input array can be repeated in an element in the output.

For example, given as inputs [2, 5, 8] and n = 223, then the following should be the output:

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

显然，任何位数少于 n 的整数都将被接受，而任何多于 n 的整数都将被拒绝。但是如何最有效地找到具有相同位数的那些？我知道的一个解决方案是嵌套 for 循环，一个用于输入整数中的每个数字，并从输入数组中形成每个可能的数字组合并检查它反对n。虽然这看起来很笨拙，但我想知道是否有更好的方法。

Answer 1

使用递归。

编写一个函数，输出与n 相同位数的所有答案。调用此函数 doit(n)。然后，它的伪代码:

1. 找到n的最高位，称之为d
2. 对于所有d1小于d的数字，输出所有以d1开头的数字
3. 从n中删除数字d；调用结果 n1
4. 调用doit(n1)；对于结果列表中的每个数字，在前面加上数字 d