[一道有趣的算法题] 各种语言都来试试吧～

用内置函数只需2行

function testArray(array $array){
sort($array);
if(array_pop($array) == array_sum($array))
return true;
return false;
}
echo testArray(array(4, 6, 23, 10, 3));

PS:你给出的例子是错的，[4, 6, 23, 10, 1, 3], 4+6+10+1+3 = 24

@AlloVince if any combination of numbers in the array can be added up to equal the largest number in the array

只会穷举的算法弱菜灰过...

目测排序后DP?
算了，还是去做毕设吧。。。

不要用排序，一次遍历求和，同时找到最大值，用和减去最大值判断是否等于最大值就可以了

背包 = =

@AlloVince 你理解错误，我给的例子没错。没要求剩下数字都要用
如：true--[1, 22, 23, 25, 26] 注：25+1 = 26

去掉最大数之后就是很典型的 01 背包问题

一场复杂的背包啊
我就选择跳过了 看楼上楼下的了

@66450146 不是吧，01背包要求非负

@kilimanjaroup 全加上最大负数的绝对值，结果作相应处理

@SonicXP
@hzlzh

sorry，没有仔细看题。

php的话更多应该是求一个数组的子集：

https://gist.github.com/AlloVince/5298390

不会背包, 只会穷举: http://codepad.org/Eb5zlSSO

http://gist.github.com/xl/5298578

穷举的危害是会有很多重复的子计算，只要在穷举基础上加上简单的防止重复子计算的措施就行了。
简单且高效。

01背包+binary search优化

这分明就是Hello, world!级的Prolog题

$ swipl
Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 6.0.2)
Copyright (c) 1990-2011 University of Amsterdam, VU Amsterdam
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software,
and you are welcome to redistribute it under certain conditions.
Please visit http://www.swi-prolog.org for details.

For help, use ?- help(Topic). or ?- apropos(Word).

?- ['addition.pl'].
% library(clpr) compiled into clpr 0.06 sec, 2,498 clauses
% library(option) compiled into swi_option 0.00 sec, 32 clauses
% pure_input compiled into pure_input 0.00 sec, 48 clauses
% library(pio) compiled into pio 0.00 sec, 52 clauses
% library(simplex) compiled into simplex 0.08 sec, 2,835 clauses
% addition.pl compiled 0.08 sec, 2,867 clauses
true.

?- once(solve([4, 6, 23, 10, 1, 3], _)).
true.

?- once(solve([4, 6, 23, 10, 1, 3], R)).
R = [{10, 1}, {6, 1}, {4, 1}, {3, 1}, {1, 0}].

?- once(solve([5, 7, 16, 1, 2], _)).
false.

?- once(solve([1, 22, 23, 24, 27, 29, 33], _)).
false.

?- once(solve([1, 22, 23, 25, 26], _)).
true.

?- once(solve([1, 22, 23, 25, 26], R)).
R = [{25, 1}, {23, 0}, {22, 0}, {1, 1}].

?- once(solve([3, 5, -1, 8, 1, -2, 12], _)).
true.

?- once(solve([3, 5, -1, 8, 1, -2, 12], R)).
R = [{8, 1}, {5, 1}, {3, 0}, {1, 0}, {-1, 1}, {-2, 0}].

?-

@bhuztez 看这里，这题的官方定级是 easy，
[Array Addition I]
http://coderbyte.com/CodingArea/Challenges/

排序后剔除max，计算剩余sum
sum < max -> false
sum = max -> true
sum > max -> combos(sum).each do |c|
sum(c) == max ? true : continue
false

肯定还有其他更好的解法，数组长了上面的程序直接PASS掉。