一个阿里巴巴笔试题

cc2005726

判断是否是数组a中任意几个数的之和
例如：
输入：x = 5；a[10] = {1,1,2,3,4,5}
输出：5 = 5； 5 = 4 + 1； 5 = 3 + 2； 5 = 3 + 1 + 1；要求算法高效率
同学说先排序，再递归，求出组合。
各位的意见呢？

Rainyboy

回复 1 # cc2005726 的帖子

贴一个不完整的吧，算是抛砖引玉……

1. def main():
   
2.     SouceData =[2,3,4,1,1,5,0];
   
3.     SouceData.sort();
   
4.     MatchData = [0];
   
5.     Search(5,SouceData,MatchData);
   
6.    
   
7. def Search(tag,SD,MD,st=0):
   
8.     if tag - SD[st] == 0:
   
9.         print MD[1:];
   
10.         return True;
    
11.     elif tag - SD[st] > 0:
    
12.         if st == len(SD):
    
13.             return False;
    
14.         else:
    
15.             for i in range(1,len(SD)-st):
    
16.                 MD.append(SD[st+i]);
    
17.                 re = Search(tag-SD[st],SD,MD,st+i)
    
18.                 MD.pop();
    
19.                 if re == True:
    
20.                     continue;
    
21.                 else: #re == False
    
22.                     return True;
    
23.             return True;
    
24.     else:
    
25.         return False;
    
26. 
    
27. 
    
28. if __name__ == '__main__':
    
29.     main();
    

复制代码

结果中存在一些重复的模式……
[1, 1, 3]
[1, 4]
[1, 4]
[2, 3]
[5]

mistuning

我只会循环着做，看来是铁定不能去阿里巴巴了

Rainyboy

回复 3 # mistuning 的帖子

但是直接遍历也许是在面试时能想出的，实现最快、实现起来BUG最少的办法了……

agrimony

算法的都是高人啊