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

[hzlzh]

## 目的
没什么目的，就是好玩，最近大伙在做一道有趣的算法题，拿来大家分享一下，有兴趣的可以试试。

## 题目描述：
Have the function ArrayAdditionI(arr) take the array of numbers stored in arr and return the string true if any combination of numbers in the array can be added up to equal the largest number in the array, otherwise return the string false. For example: if arr contains [4, 6, 23, 10, 1, 3] the output should return true because 4 + 6 + 10 + 3 = 23. The array will not be empty, will not contain all the same elements, and may contain negative numbers.

## 也就是说：
如：[4, 6, 23, 10, 1, 3] 这个数组(数字不重复，可以为负数)中选出最大的数字是 23
4+6+10+3 = 23
然后剩余的任意个数字数相加之和若等于23，则 true，否则false

## 测试用例：
输出--输入
false--[5, 7, 16, 1, 2]
false--[1, 22, 23, 24, 27, 29, 33]
true--[1, 22, 23, 25, 26] 注：25+1 = 26
true--[3, 5, -1, 8, 1, -2, 12] 注：5+(-1)+8 = 12

## 要求：
书写语言不限，不能是思路或伪代码，用如: php,python,js...等都可以在网站里运行检查

## 出处：
题目来源：
http://coderbyte.com/
时间要求：当然是越快越好

enjoy!

ps: 写出来的童鞋可以 [只贴Gist ID，如：/xxxx/123456] ，你懂得，别影响了别人思路。

[AlloVince]

用内置函数只需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

[SonicXP]

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

[alexrezit]

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

[best1a]

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

[xunyu]

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

[200]

背包 = =

[hzlzh]

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

[66450146]

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

[lookhi]

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

[ftwbzhao]

https://gist.github.com/ftwbzhao/5298212

[kilimanjaroup]

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

[zxc111]

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

[AlloVince]

@SonicXP
@hzlzh

sorry，没有仔细看题。

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

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

[limu]

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

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

[RisingV]

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

[laskuma]

01背包+binary search优化

[bhuztez]

这分明就是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}].

?-

[hzlzh]

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

[hpyhacking]

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

[hpyhacking]

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