给定数字n，数组arr={1,3,5,2}，求arr中的数字能组

字节-算法面试题：给定数字n和集合arr，求arr中的数字能组成小于n的最大整数，arr中的数字可以重复使用。
例：n=5213，arr={0,3,5,2}，返回结果应该为5205。

解题思路

按位先正向后反向查找，使用递归实现功能。
需要特别注意的是：首位和末位，正向递归时判断是否是末位，回溯时判断是否是首位。

正向查找

根据n的位数，从大数位到小数位进行递归：如果当前数字可用，就将当前数字放入该位置。
特殊情况：如果是最后一位，需要将 比当前数字更小的最大数字 放到该位置上。

无匹配

如果当前数字无匹配，将 比当前数字更小的最大数字 放到该位置上，同时后续数位都填充最大数字。

回溯-反向查找

如果没有 比当前数字更小的最大数字，则回溯到上一位置，将 比当前数字更小的最大数字 放到该位置上，同时后续数位都填充最大数字。
特殊情况：如果回溯到首位仍然没有 比当前数字更小的最大数字，则取消最大位，同时后续数位都填充最大数字。

编程思路

1. 回溯时，一定会查找 比当前数字更小的最大数字 是否存在，与“无匹配”的功能重复，所以可以写到同1个函数中；
2. 正向查找和回溯时，传递参数为当前的位置，所以可以将当前位置position作为传参；
3. 最后判断position的位置，并将之后的位置全部填充为可用的最大值。

Python代码

n = 5213
arr = {0,3,5,2}

arr_list_sort = sorted(list(arr))       # 排序可用数字，以便于查找 比当前数字更小的最大数字
n = str(n)
n_len = len(n) 
res = [arr_list_sort[0]] * n_len        # 使用最小值初始化所有位置

def fan(position):
    """回溯-反向递归，并判断是否存在比当前数字更小的数字
    position[int]: 当前位置
    """
    # print("position = ", position)
    np = int(n[position])
    if position == 0:       # 回溯到首位
        for arrr in arr_list_sort[::-1]:
            if arrr<np:         # 存在比当前数字更小的数字
                res[position] = arrr
                return position
        position = -1
        res.pop(0)
        return position
    else:
        for arrr in arr_list_sort[::-1]:
            if arrr<np:         # 存在比当前数字更小的数字
                res[position] = arrr
                return position
        return fan(position-1)

def zheng(position):
    """正向递归
    position[int]: 当前位置
    """
    np = int(n[position])
    if position < n_len-1:
        if np not in arr:
            position = fan(position)
            return position
        else:            
            res[position] = np
            return zheng(position+1)
    else:   # 最后一位
        position = fan(position)
        return position

position = zheng(position=0)
lenres = len(res)

if lenres == 0:                     # n为1位数字 且 arr中没有比n更小的数字
    res = "无结果！"
else:
    if position != n_len-1:         # 没有处理到最后一位
        position += 1
        for _ in res[position:]:    # 后续位置填充可用的最大值
            res[position] = arr_list_sort[-1]
    res = sum([pow(10,i)*j for i,j in enumerate(res[::-1])]) 

print(res)

个人原创，欢迎交流讨论！