（不一样的递归思想，值得再看。）
题目链接：
# https://exp-blog.com/algorithm/poj/poj1416-shredding-company/ # https://blog.csdn.net/lyy289065406/article/details/6647969
一?特别注意
1. 关于递归思路，参考别人的设计思想：
? ? ? ? 以“12346”为例，当进行深度搜索时：
????????第一步，先切下一个“1”，然后递归去切“2346”；
????????第二步，再切下一个“12”，然后递归去切“346”；
????????第三步，再切下一个“123”，然后递归去切“46”；
????????第四步，再切下一个“1234” 然后递归去切“6”
????????第五步，再切下“12346”。
PS：我没有进行第五步拆分，而是在初始阶段对第五步这种特殊情况进行了判断处理；这样的话，可以保证每次拆分字符串都可以拆成前后两段：
## 循环
E = len(Data)
store = []
for i in range(E-1): # 拆成前后两个字符串
store.append([Data[:(i+1)],Data[i+1:]])2.?特别地，当遇到满足条件的方案后，要考虑特殊处理：
2.1?将当前方案加入到列表中，继续分析：
????????2.2.1 当前方案中节点长度大于1时，算法不进行回溯，而是继续执行，寻找新的可行方案
????????2.2.2?当前方案中节点的长度为1时，算法进行回溯；回溯之后，弹出当前的节点，再继续寻找新的方案，而不是return至上一层。
? ? ? ? 2.2.3?特别注意：在执行上述过程时，要修改相应的参数信息。（具体见dfs子程序）
2.2?另外，递归过程不要直接更新队列的值，也不要将队列直接赋值给新变量。否则，队列一经修改，其他变量也会更改。
二?代码实现
# POJ 1416 - Shredding Company
# https://exp-blog.com/algorithm/poj/poj1416-shredding-company/
# https://blog.csdn.net/lyy289065406/article/details/6647969
import collections
class Solution:
def DFS(self,target,subData):
self.target = int(target)
# 记录方案
self.ways = collections.defaultdict(list)
# 记录出现的Sum的类别及数目
self.Sum_dict = collections.defaultdict(list)
# 给定一个初始Sum值0，找到一个最大且不超过Target的Sum，并且记录该方案至self.ways
# 初始Sum
self.Sum_pre = 0
self.dfs(subData,0,[],False)
return self.ways
def dfs(self,Data,Sum,parent,Flag):
# 1 对于队列而言，首先将其转存为新的变量，便于实现回溯时的状态恢复
new_parent = []
for i in parent:
new_parent.append(i)
## 2 判断是否终止
if Flag == True:# 是否叠加到了最后一串字符呢？
# 求和
Sum = Sum + int(Data)
if Sum >= self.Sum_pre and Sum<= self.target:
# 更新获取更大的和
self.Sum_pre = Sum
# 保存当前的节点Sum
self.Sum_dict[Sum] = self.Sum_dict.get(Sum,0) + 1; # 统计出现同一Sum的次数
## 将方案保存
# new_parent.append(Data)
temp_way = [] #为了防止new_parent引起self.ways更新，此处重新赋值
for i in new_parent:
temp_way.append(i)
temp_way.append(Data)
self.ways[Sum].append(temp_way)
## 特别处理——当Data仍然可拆分时，需要进一步拆分
if len(Data)>=2: #当Data仍然可拆分时，需要进一步拆分
# 这里要恢复new_parent
# new_parent.pop() #弹出最后加入的点
Sum = Sum - int(Data) # 拆分之前，恢复数据
else:
return # 如果没必要再分，就结束吧！
else:
Sum = Sum - int(Data) #恢复数据
## 3 循环
E = len(Data)
store = []
for i in range(E-1): # 拆成前后两个字符串
store.append([Data[:(i+1)],Data[i+1:]])
for i in range(len(store)): # 对每一组字符串进行DFS搜索处理
## 第一段不递归
sub1 = store[i][0]
Sum_new = Sum + int(sub1) # 这里需要重新赋值，以便于回溯时恢复参数状态
if Sum_new > self.target: # 如果部分和超过了目标，则返回
return
## 第二段递归
new_parent.append(sub1)
sub2 = store[i][1]
self.dfs(sub2, Sum_new, new_parent, True)
## 奇葩的处理：这里不返回，而是继续执行下一次的循环
# 循环之前，弹出节点，恢复一下列表参数
new_parent.pop()
return
## 迎接输入：
data = [] #利用队列存储目标和数据
while True:
str1,str2 = input().strip().split(' ')
if int(str1)==0 and int(str2)==0:
break
else:
data.append([str1,str2])
# print(data)
# 共计N组数据
N = len(data)
# print(N)
for i in range(N):
# 获得目标和数据
target,subData = data[i][0],data[i][1]
## 第一级判别：目标与数据是否直接相等——是：打印数据
if target == subData:
print(target+' '+subData)
continue # 去执行下一次循环
## 第二级判别：按元素个数划分，其和是否大于目标——
# 数据元素个数
E = len(subData)
# print(E)
# 计算E个元素之和sum
E_sum = 0
for i in range(E):
E_sum = E_sum + int(subData[i])
if E_sum > int(target):# 按元素个数划分，其和是否大于目标——是：打印error
print("error")
continue
if E_sum == int(target) and '0' not in subData:# 按元素个数划分，其和是否等于目标，并且数据中无0元素——是：打印出来
res = target
for i in range(E):
res = res + ' ' + subData[i]
print(res)
continue
## 接下里，利用DFS处理一般情形——
test = Solution()
ways = test.DFS(target,subData)
# 处理输出结果
MAX_Sum = max(ways.keys()); #查找接近于目标的最大和
ans = ways[MAX_Sum] #获取相应的方案
if len(ans)>1: # 当存在多种方案时
print("rejected")
else:
# 按照格式打印输出
ans_sum = 0
res = ''
for i in ans[0]:
ans_sum += int(i)
res = res + ' ' + i
print(str(ans_sum) + ' ' + res.strip(' '))
输入：
50 12346
376 144139
927438 927438
18 3312
9 3142
25 1299
111 33333
103 862150
6 1104
0 0输出：
43 1 2 34 6
283 144 139
927438 927438
18 3 3 12
error
21 1 2 9 9
rejected
103 86 2 15 0
rejected