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

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

这道题实质上就是求一个数组所有的子集，下面用python实现一个，使用的二进制取位来列举所有的子集
test1 = [5, 7, 16, 1, 2]
test2 = [1, 22, 23, 24, 27, 29, 33]
test3 = [1, 22, 23, 25, 26]
test4 = [3, 5, -1, 8, 1, -2, 12]

def getSubArraySum(array,index):
arrayLength = len(array)
sum = 0
for i in range(arrayLength):
if (index>>(arrayLength - i - 1))&1 == 1:
sum += array[i]
return sum
def checkArray(array):
tempArray = array
maxValue = max(tempArray)
del tempArray[tempArray.index(maxValue)]
istrue = False
for i in range(2**len(tempArray)):
if maxValue == getSubArraySum(array,i):
istrue = True
return istrue
return istrue

print checkArray(test1)
print checkArray(test2)
print checkArray(test3)
print checkArray(test4)

错了一点，上面if maxValue == getSubArraySum(array,i):应该为if maxValue == getSubArraySum(tempArray,i):

Haskell:

import Data.List

chkArr :: Int -> [Int] -> Bool
chkArr amount arr
| amount == 0 = True
| null arr || amount < 0 = False
| otherwise = chkArr (amount-(head arr)) (tail arr) || chkArr amount (tail arr)

testArr :: [Int] -> Bool
testArr xs = chkArr (head ys) (tail ys)
where ys = sortBy (flip compare) xs

https://gist.github.com/monkeylyf/5315975

”if any combination of numbers in the array can be added up to equal the largest number in the array“ 我对题目的理解是任意组合加起来等于最大的那个, 没说任意组合里不可以有最大的这个数
所以有一个test case 说我的结果不正确:[10,12,500,1,-5,1,0]
私以为, 所以存在组合0 + 500 = 500. 应该return true

思路是0/1 knapsack 没有优化 目测这个网站的大数据测试很水

@monkeylyf 如果可以包含最大那个元素, 那肯定都要返回true了, 因为最大元素自己肯定等于自己.

@skywalker 有道理. 题目可以写的再清晰点.

又看了下题目 这题含有负数 背包解不了 还是直接穷举吧

@monkeylyf 用递归做一个最优递归。

@xunyu 不要用排序，一次遍历求和，同时找到最大值，用和减去最大值判断是否等于最大值就可以了
+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 +1 +1 +1

@xunyu
@lehui99 建议仔细看下题目和用例。
true--[1, 22, 23, 25, 26] 注：25+1 = 26