【华为OD机试2023】组合出合法最小数Python

题目描述：

给一个数组，数组里面都是代表非负整数的字符串，将数组里所有的数值排列组合拼接起来组成一个数字，输出拼接成的最小的数字。

输入描述：

一个数组，数组不为空，数组里面都是代表非负整数的字符串，可以是0开头，例如：["13", "045", "09", "56"]。

数组的大小范围：[1, 50]

数组中每个元素的长度范围：[1, 30]

输出描述：

以字符串的格式输出一个数字，如果最终结果是多位数字，要优先选择输出不是“0”开头的最小数字；如果拼接出的数字都是“0”开头，则选取值最小的，并且把开头部分的“0”都去掉再输出；如果是单位数“0”，可以直接输出“0”

示例1

输入：

20 1

输出：

120

说明：

["20", "1"]能组成 201和120， 其中120比较小

示例2

输入：

08 10 2

输出：

10082

说明：

["08", "10", "2"]能组成 08102、 08210、10082、10208、20810、21008等数字，其中"0"开头的08102和08201排除，选择最小的10082输出

示例3

输入：

01 02

输出：

102

说明：

["01", "02"]能拼接成0102和0201，都是“0”开头，选取较小的0102，去掉前面的0，输出102

解题思路：

把所有数字按照首位、次位、再次位....的大小升序排列，那么在排序后的列表首位的一定是最小的。

逐个遍历新列表中的数字，如果第一个数字的首位不是0，那么直接将列表转为字符串输出；如果是0，那么继续向后遍历，直到遍历到第一个首位不是0的数字，此时将这个数字和列表首位的数字拼接成新字符串，把这个数字所在的列表位改为空字符串，然后输出字符串。

如果遍历到最后，所有数字的首位都是0，那么就直接转为字符串输出，去掉首位的0

#回溯法求全排列，时间复杂度肯定不行，但还没找到更好的方法，理论上解题思路的方法更好，但之前写的是错的
lst=input().split()
l=len(lst)
res=[]
path=[]
used=[0]*l
def backtracking(res,path,used):
    if len(path)==l:
        res.append(''.join(path))
        return
    for i in range(l):
        if used[i]!=1:
            path.append(lst[i])
            used[i]=1
            backtracking(res,path,used)
            used[i]=0
            path.pop()
backtracking(res,path,used)
bdyl=[]
for item in res:
    if item[0]!='0':
        bdyl.append(item)
if bdyl:
    print(min(bdyl))
else:
    print(min(res)[1:])