回文字符串分解的代码效率+时间成本澄清

Question

问题1：

对于生成给定字符串的所有回文分解的问题，作者提供了以下解决方案：

def palindromic_decompositions(input):
  def directed_palindrome_partitioning(offset, partial_partition):
    if offset == len(input):
      result.append(list(partial_partition))
      return 

    for i in range(offset + 1, len(input) + 1):
      prefix = input[offset:i]
      if prefix == prefix[::-1]:
        directed_palindrome_partitioning(i, partial_partition + [prefix])

  result = []
  directed_palindrome_partitioning(0, [])
  return result

在第4行，您将看到partial_partition包装在list()函数中，它实际上只是制作partial partition的副本并将其附加到结果中

然而，由于我们从不改变部分分区，我认为这是对partial_partition的浪费性重复。每个函数调用只是将部分分区重新分配给参数。我的理解正确吗

我运行了这段代码，并在下面的输入案例中运行了一个不带list()的代码副本：(palindromic_decompositions('0204451881')，得到了相同的输出

问题2: 提供的问题时间成本为nx（2^n），但没有提供解释。我理解n部分是因为list(partial_partition)->；有人能解释一下（2^n）是从哪里来的吗

Answer 1

对于Q1：list()是多余的，因为partial_partition + [prefix]也会生成副本。否则，没有它result将被指向同一底层对象的指针填充