给定数字列表如何生成所有元素排列的和并返回对应和的数组

假设我们有一个数字列表 [1,2,3]，需要将元素所有排列对应的前缀和全部添加到结果数组中并返回该数组，请问如何实现？

求和过程示例 #

1 = 1（第一个元素，直接添加到结果数组ans中）
1 + 2 = 3
1 + 3 = 4
1 + 2 + 3 = 6
1 + 3 + 2 = 6
2 = 2（第二个元素，直接添加到结果数组ans中）
2 + 1 = 3
2 + 3 = 5
2 + 1 + 3 = 6
2 + 3 + 1 = 6
3 = 3（第三个元素，直接添加到结果数组ans中）
3 + 1 = 4
3 + 2 = 5
3 + 1 + 2 = 6
3 + 2 + 1 = 6

最终返回的结果数组为 [1,3,4,6,6,2,3,5,6,6,3,4,5,6,6]

思路梳理 #

核心逻辑是按原列表的元素顺序作为排列的起始元素，依次生成所有可能长度的排列，计算每个排列的总和（对应题目要求的前缀和）并加入结果数组即可：

1. 遍历原列表的每一个元素作为排列的起始点，首先将该元素本身加入结果数组（对应长度为1的排列）
2. 对每个起始点，取剩余元素生成长度为1到n-1的所有排列，依次计算「起始点 + 排列所有元素的和」，加入结果数组
3. 所有起始点处理完成后得到的数组就是目标结果

代码实现（Python） #

from itertools import permutations

def get_perm_sum_array(nums):
    res = []
    n = len(nums)
    for start in nums:
        # 添加长度为1的排列和
        res.append(start)
        rest_nums = [x for x in nums if x != start]
        # 遍历排列长度从2到n
        for perm_len in range(2, n+1):
            # 生成剩余元素中取perm_len-1个的所有排列
            for p in permutations(rest_nums, perm_len - 1):
                current_sum = start + sum(p)
                res.append(current_sum)
    return res

# 测试验证
if __name__ == "__main__":
    test_nums = [1,2,3]
    print(get_perm_sum_array(test_nums))
    # 输出：[1, 3, 4, 6, 6, 2, 3, 5, 6, 6, 3, 4, 5, 6, 6]

内容的提问来源于stack exchange，提问作者pi2018