如何找到给定列表中的字符串组合，这些字符串加起来就是某个字符串（没有外部库）

Question

如果要形成的字符串是'abcde'，而输入列表是['abc', 'd', 'ac', 'ab', 'e', 'abcd'] 形成字符串“abcde”的不同方法如下

（一）

（2）'abcd'+'e'

因此答案是2

我如何处理这个问题

我迄今为止的进展

character1 = input()
n = int(input())    # number of allowed inputs for list
list1 = [input() for i in range(n)]

Answer 1

可以使用递归生成器函数：

d, s = ['abc', 'd', 'ac', 'ab', 'e', 'abcd'], 'abcde'
def get_combos(d, c = []):
  if ''.join(c) == s:
     yield c
  else:
     for i in d:
        if s.startswith(''.join(c)+i):
           yield from get_combos(d, c+[i])

print(list(get_combos(d)))

输出：

[['abc', 'd', 'e'], ['abcd', 'e']]