苏晓晓 发表于 2013-8-16 10:02:05

[经典算法] 一个阿里巴巴笔试题

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

王培培 发表于 2013-8-16 10:11:34

贴一个不完整的吧，算是抛砖引玉……1.def main():2.    SouceData=;3.    SouceData.sort();4.    MatchData = ;5.    Search(5,SouceData,MatchData);6.7.def Search(tag,SD,MD,st=0):8.    if tag - SD == 0:9.       print MD;10.       return True;11.    elif tag - SD > 0:12.      ifst == len(SD):13.         return False;14.       else:15.         for i in range(1,len(SD)-st):16.               MD.append(SD);17.               re = Search(tag-SD,SD,MD,st+i)18.               MD.pop();19.               if re == True:20.                   continue;21.               else: #re == False22.                   return True;23.         return True;24.    else:25.       return False;26.27.28.if __name__ == '__main__':29.    main();结果中存在一些重复的模式……
页: [1]
查看完整版本: [经典算法] 一个阿里巴巴笔试题