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

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

## 此题目的原地址：
http://coderbyte.com/CodingArea/information.php?ct=Array%20Addition%20I
## 官方定级：easy

[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掉。

[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