arrays - 整数数组的所有子部分的总和

给定一个数组，它的子部分被定义为{1,3,5,7}。
我必须在新数组中找到所有这些数字的和。在这种情况下，总和是2333。
请帮助我在{1357,135,137,157,357,13,15,17,35,37,57,1,3,5,7}中找到解决方案。我的解决方案超时了。
问题的链接是here或here。
我目前的尝试是

for(I=0 to len) //len is length of the array
{
     for(j=0 to len-i)
     {
          sum+= arr[I]*pow(10,j)*((len-i) C i)*pow(2,i)
     }
}

换句话说-len-i C i=（右边的整数个数）C权重（组合{来自排列和组合}）
2^i=2次方（左整数个数）
谢谢

最佳答案

用一个简单的递归就可以轻松地解决这个问题。

def F(arr):
    if len(arr) == 1:
        return (arr[0], 1)
    else:
        r = F(arr[:-1])
        return (11 * r[0] + (r[1] + 1) * arr[-1], 2 * r[1] + 1)

那么，它是如何工作的呢？很简单。假设我们要计算{1,3,5,7}所有子部分的和。假设我们知道{1,3,5}的组合数和{1,3,5}的子部分之和，并且我们可以使用以下公式轻松计算{1,3,5,7}：
SUMIN子部分（{1，3，5，7}）＝11×SUMIN子部分（{1，3，5}）+ NUBYBY组合（{1，3，5}）* 7＋7
这个公式通过观察很容易得出。假设我们有{1,3,5}的所有组合

A = [135, 13, 15, 35, 1, 3, 5]

我们可以通过

A = [135, 13, 15, 35, 1, 3, 5] +
    [135 * 10 + 7,
     13  * 10 + 7,
     15  * 10 + 7,
     35  * 10 + 7,
     1   * 10 + 7,
     3   * 10 + 7,
     5   * 10 + 7] + [7]