你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
你如何从给定的N个数字中测试所有可能的加法组合,使它们加起来得到给定的最终数字?
一个简单的例子:
要添加的数字集:N ={1,5,22,15,0,…} 期望结果:12345
当前回答
首先推导0。0是加法的一个恒等式所以在这个特殊情况下,它在单类定律下是没有用的。如果你想向上爬到一个正数,也可以推导出负数。否则还需要做减法运算。
所以…在这个特定的作业中,你能得到的最快算法如下所示。
函数items2T ([n,……ns), t) { Var c = ~~(t/n); 返回ns。长度呢?数组(c + 1) .fill () .reduce((r,_,i) => r.concat(items2T(ns, t-n*i)。map(s => Array(i).fill(n).concat(s))),[]) : t % n ?[] :[数组(c) .fill (n)); }; Var数据= [3,9,8,4,5,7,10], 结果; console.time(“组合”); result = items2T(data, 15); console.timeEnd(“组合”); console.log (JSON.stringify(结果));
这是一个非常快的算法,但如果你对数据数组进行降序排序,它会更快。使用.sort()是无关紧要的,因为算法最终会减少递归调用。
其他回答
另一个python解决方案是使用itertools.combination模块,如下所示:
#!/usr/local/bin/python
from itertools import combinations
def find_sum_in_list(numbers, target):
results = []
for x in range(len(numbers)):
results.extend(
[
combo for combo in combinations(numbers ,x)
if sum(combo) == target
]
)
print results
if __name__ == "__main__":
find_sum_in_list([3,9,8,4,5,7,10], 15)
输出:[(8,7),(5,10),(3,8,4),(3,5,7)]
Java解决方案的Swift 3转换(by @JeremyThompson)
protocol _IntType { }
extension Int: _IntType {}
extension Array where Element: _IntType {
func subsets(to: Int) -> [[Element]]? {
func sum_up_recursive(_ numbers: [Element], _ target: Int, _ partial: [Element], _ solution: inout [[Element]]) {
var sum: Int = 0
for x in partial {
sum += x as! Int
}
if sum == target {
solution.append(partial)
}
guard sum < target else {
return
}
for i in stride(from: 0, to: numbers.count, by: 1) {
var remaining = [Element]()
for j in stride(from: i + 1, to: numbers.count, by: 1) {
remaining.append(numbers[j])
}
var partial_rec = [Element](partial)
partial_rec.append(numbers[i])
sum_up_recursive(remaining, target, partial_rec, &solution)
}
}
var solutions = [[Element]]()
sum_up_recursive(self, to, [Element](), &solutions)
return solutions.count > 0 ? solutions : nil
}
}
用法:
let numbers = [3, 9, 8, 4, 5, 7, 10]
if let solution = numbers.subsets(to: 15) {
print(solution) // output: [[3, 8, 4], [3, 5, 7], [8, 7], [5, 10]]
} else {
print("not possible")
}
Java非递归版本,简单地添加元素并在可能的值之间重新分配它们。0被忽略,适用于固定的列表(给定的是您可以使用的)或可重复的数字列表。
import java.util.*;
public class TestCombinations {
public static void main(String[] args) {
ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(0, 1, 2, 2, 5, 10, 20));
LinkedHashSet<Integer> targets = new LinkedHashSet<Integer>() {{
add(4);
add(10);
add(25);
}};
System.out.println("## each element can appear as many times as needed");
for (Integer target: targets) {
Combinations combinations = new Combinations(numbers, target, true);
combinations.calculateCombinations();
for (String solution: combinations.getCombinations()) {
System.out.println(solution);
}
}
System.out.println("## each element can appear only once");
for (Integer target: targets) {
Combinations combinations = new Combinations(numbers, target, false);
combinations.calculateCombinations();
for (String solution: combinations.getCombinations()) {
System.out.println(solution);
}
}
}
public static class Combinations {
private boolean allowRepetitions;
private int[] repetitions;
private ArrayList<Integer> numbers;
private Integer target;
private Integer sum;
private boolean hasNext;
private Set<String> combinations;
/**
* Constructor.
*
* @param numbers Numbers that can be used to calculate the sum.
* @param target Target value for sum.
*/
public Combinations(ArrayList<Integer> numbers, Integer target) {
this(numbers, target, true);
}
/**
* Constructor.
*
* @param numbers Numbers that can be used to calculate the sum.
* @param target Target value for sum.
*/
public Combinations(ArrayList<Integer> numbers, Integer target, boolean allowRepetitions) {
this.allowRepetitions = allowRepetitions;
if (this.allowRepetitions) {
Set<Integer> numbersSet = new HashSet<>(numbers);
this.numbers = new ArrayList<>(numbersSet);
} else {
this.numbers = numbers;
}
this.numbers.removeAll(Arrays.asList(0));
Collections.sort(this.numbers);
this.target = target;
this.repetitions = new int[this.numbers.size()];
this.combinations = new LinkedHashSet<>();
this.sum = 0;
if (this.repetitions.length > 0)
this.hasNext = true;
else
this.hasNext = false;
}
/**
* Calculate and return the sum of the current combination.
*
* @return The sum.
*/
private Integer calculateSum() {
this.sum = 0;
for (int i = 0; i < repetitions.length; ++i) {
this.sum += repetitions[i] * numbers.get(i);
}
return this.sum;
}
/**
* Redistribute picks when only one of each number is allowed in the sum.
*/
private void redistribute() {
for (int i = 1; i < this.repetitions.length; ++i) {
if (this.repetitions[i - 1] > 1) {
this.repetitions[i - 1] = 0;
this.repetitions[i] += 1;
}
}
if (this.repetitions[this.repetitions.length - 1] > 1)
this.repetitions[this.repetitions.length - 1] = 0;
}
/**
* Get the sum of the next combination. When 0 is returned, there's no other combinations to check.
*
* @return The sum.
*/
private Integer next() {
if (this.hasNext && this.repetitions.length > 0) {
this.repetitions[0] += 1;
if (!this.allowRepetitions)
this.redistribute();
this.calculateSum();
for (int i = 0; i < this.repetitions.length && this.sum != 0; ++i) {
if (this.sum > this.target) {
this.repetitions[i] = 0;
if (i + 1 < this.repetitions.length) {
this.repetitions[i + 1] += 1;
if (!this.allowRepetitions)
this.redistribute();
}
this.calculateSum();
}
}
if (this.sum.compareTo(0) == 0)
this.hasNext = false;
}
return this.sum;
}
/**
* Calculate all combinations whose sum equals target.
*/
public void calculateCombinations() {
while (this.hasNext) {
if (this.next().compareTo(target) == 0)
this.combinations.add(this.toString());
}
}
/**
* Return all combinations whose sum equals target.
*
* @return Combinations as a set of strings.
*/
public Set<String> getCombinations() {
return this.combinations;
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder("" + sum + ": ");
for (int i = 0; i < repetitions.length; ++i) {
for (int j = 0; j < repetitions[i]; ++j) {
stringBuilder.append(numbers.get(i) + " ");
}
}
return stringBuilder.toString();
}
}
}
样例输入:
numbers: 0, 1, 2, 2, 5, 10, 20
targets: 4, 10, 25
样例输出:
## each element can appear as many times as needed
4: 1 1 1 1
4: 1 1 2
4: 2 2
10: 1 1 1 1 1 1 1 1 1 1
10: 1 1 1 1 1 1 1 1 2
10: 1 1 1 1 1 1 2 2
10: 1 1 1 1 2 2 2
10: 1 1 2 2 2 2
10: 2 2 2 2 2
10: 1 1 1 1 1 5
10: 1 1 1 2 5
10: 1 2 2 5
10: 5 5
10: 10
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2
25: 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2
25: 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2
25: 1 1 1 2 2 2 2 2 2 2 2 2 2 2
25: 1 2 2 2 2 2 2 2 2 2 2 2 2
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 5
25: 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 5
25: 1 1 1 1 1 1 1 1 2 2 2 2 2 2 5
25: 1 1 1 1 1 1 2 2 2 2 2 2 2 5
25: 1 1 1 1 2 2 2 2 2 2 2 2 5
25: 1 1 2 2 2 2 2 2 2 2 2 5
25: 2 2 2 2 2 2 2 2 2 2 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 5 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 5 5
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 5 5
25: 1 1 1 1 1 1 1 1 1 2 2 2 5 5
25: 1 1 1 1 1 1 1 2 2 2 2 5 5
25: 1 1 1 1 1 2 2 2 2 2 5 5
25: 1 1 1 2 2 2 2 2 2 5 5
25: 1 2 2 2 2 2 2 2 5 5
25: 1 1 1 1 1 1 1 1 1 1 5 5 5
25: 1 1 1 1 1 1 1 1 2 5 5 5
25: 1 1 1 1 1 1 2 2 5 5 5
25: 1 1 1 1 2 2 2 5 5 5
25: 1 1 2 2 2 2 5 5 5
25: 2 2 2 2 2 5 5 5
25: 1 1 1 1 1 5 5 5 5
25: 1 1 1 2 5 5 5 5
25: 1 2 2 5 5 5 5
25: 5 5 5 5 5
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 10
25: 1 1 1 1 1 1 1 1 1 1 1 1 1 2 10
25: 1 1 1 1 1 1 1 1 1 1 1 2 2 10
25: 1 1 1 1 1 1 1 1 1 2 2 2 10
25: 1 1 1 1 1 1 1 2 2 2 2 10
25: 1 1 1 1 1 2 2 2 2 2 10
25: 1 1 1 2 2 2 2 2 2 10
25: 1 2 2 2 2 2 2 2 10
25: 1 1 1 1 1 1 1 1 1 1 5 10
25: 1 1 1 1 1 1 1 1 2 5 10
25: 1 1 1 1 1 1 2 2 5 10
25: 1 1 1 1 2 2 2 5 10
25: 1 1 2 2 2 2 5 10
25: 2 2 2 2 2 5 10
25: 1 1 1 1 1 5 5 10
25: 1 1 1 2 5 5 10
25: 1 2 2 5 5 10
25: 5 5 5 10
25: 1 1 1 1 1 10 10
25: 1 1 1 2 10 10
25: 1 2 2 10 10
25: 5 10 10
25: 1 1 1 1 1 20
25: 1 1 1 2 20
25: 1 2 2 20
25: 5 20
## each element can appear only once
4: 2 2
10: 1 2 2 5
10: 10
25: 1 2 2 20
25: 5 20
我想我应该用这个问题的答案,但我不能,所以这是我的答案。它使用的是《计算机程序的结构和解释》中答案的修改版本。我认为这是一个更好的递归解,应该更能取悦纯粹主义者。
我的答案是用Scala(如果我的Scala很烂,我很抱歉,我刚刚开始学习)。findsumcombination的疯狂之处在于对递归的原始列表进行排序和惟一,以防止欺骗。
def findSumCombinations(target: Int, numbers: List[Int]): Int = {
cc(target, numbers.distinct.sortWith(_ < _), List())
}
def cc(target: Int, numbers: List[Int], solution: List[Int]): Int = {
if (target == 0) {println(solution); 1 }
else if (target < 0 || numbers.length == 0) 0
else
cc(target, numbers.tail, solution)
+ cc(target - numbers.head, numbers, numbers.head :: solution)
}
使用它:
> findSumCombinations(12345, List(1,5,22,15,0,..))
* Prints a whole heap of lists that will sum to the target *
我不喜欢上面看到的Javascript解决方案。下面是我使用部分应用、闭包和递归构建的一个:
好的,我主要关心的是,如果组合数组能满足目标要求,希望这样你就能找到剩下的组合了
这里只需要设置目标并传递组合数组。
function main() {
const target = 10
const getPermutationThatSumT = setTarget(target)
const permutation = getPermutationThatSumT([1, 4, 2, 5, 6, 7])
console.log( permutation );
}
我提出的当前实现
function setTarget(target) {
let partial = [];
return function permute(input) {
let i, removed;
for (i = 0; i < input.length; i++) {
removed = input.splice(i, 1)[0];
partial.push(removed);
const sum = partial.reduce((a, b) => a + b)
if (sum === target) return partial.slice()
if (sum < target) permute(input)
input.splice(i, 0, removed);
partial.pop();
}
return null
};
}