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

[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] ，你懂得，别影响了别人思路。

[breakind]

这道题实质上就是求一个数组所有的子集，下面用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)

[breakind]

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

[skywalker]

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

[monkeylyf]

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 没有优化 目测这个网站的大数据测试很水

[skywalker]

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

[monkeylyf]

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

[monkeylyf]

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

[hzlzh]

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

[lehui99]

@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

[hzlzh]

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