给定一个数字列表，你如何创建所有和的组合以及 return 这些和的列表

Question

让我们假设我们有一个数字列表 [1,2,3] 并且我们必须附加数组中元素总和的所有可能组合和 return 该数组？

如何得到下面的和

1 = 1 (the first element so simply add it to the ans array)
1 + 2 = 3
1 + 3 = 4
1 + 2 + 3 = 6
1 + 3 + 2 = 6
2 = 2 (second element so simply add it to ans array)
2 + 1 = 3
2 + 3 = 5
2 + 1 + 3 = 6
2 + 3 + 1 = 6
3 + 1 = 4
3 = 3 (third element so simply add it to ans array)
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]

Answer 1

使用itertools:

import itertools

nums = [1,2,3]
results = []

def split(a, n):
    k, m = divmod(len(a), n)
    return [a[i*k+min(i, m):(i+1)*k+min(i+1, m)] for i in range(n)]
        
for i in range(len(nums)):
    results.append(split(list(map(sum,itertools.permutations(nums,i+1))),len(nums)))

results = zip(*results)
results = list(itertools.chain.from_iterable(itertools.chain.from_iterable(results)))

print(results)
>>> [1, 3, 4, 6, 6, 2, 3, 5, 6, 6, 3, 4, 5, 6, 6]

Answer 2

使用itertools.permutations:

>>> import itertools
>>> nums = [1, 2, 3]
>>> [sum(p) for n in range(1, len(nums)+1) for p in itertools.permutations(nums, n)]
[1, 2, 3, 3, 4, 3, 5, 4, 5, 6, 6, 6, 6, 6, 6]

如果您想确切地看到 permutations 在做什么，而不仅仅是看到最后的总和，您可以使用 map 和 join:

做一些有趣的事情

>>> [f"{'+'.join(map(str, p))}={sum(p)}" for n in range(1, len(nums)+1) for p in itertools.permutations(nums, n)]
['1=1', '2=2', '3=3', '1+2=3', '1+3=4', '2+1=3', '2+3=5', '3+1=4', '3+2=5', '1+2+3=6', '1+3+2=6', '2+1+3=6', '2+3+1=6', '3+1+2=6', '3+2+1=6']

Answer 3

这是递归问题的一个很好的例子。

要解决这个问题，您需要一个能够自行调用并在给定条件处停止的函数。

const getResults = (numbers, usedNumbers, results) => {
  if (usedNumbers.length >= numbers.length) return;

  numbers.forEach(number => {
    if (usedNumbers.includes(number)) return;

    const result = usedNumbers.reduce((acc, curr) => acc + curr, number);
    console.log(`${[...usedNumbers, number].join(' + ')} = ${result}`)
    results.push(result);
  });

  numbers.forEach(number => {
    if (! usedNumbers.includes(number)) getResults(numbers, [...usedNumbers, number], results);
  })
};

const numbers = [1,2,3];
const results = [];
numbers.forEach(number => {
  results.push(number);
  console.log(`${number} = ${number}`)
  getResults(numbers, [number], results);
});

console.log(results);

给定一个数字列表，你如何创建所有和的组合以及 return 这些和的列表

Given a list of numbers, how do you create all the combinations of sums and return a list of those sum

python

algorithm

backtracking