研发埠

标题: [经典算法] 一个阿里巴巴笔试题 [打印本页]

---

作者: 苏晓晓    时间: 2013-8-16 10:02
标题: [经典算法] 一个阿里巴巴笔试题
判断是否是数组a中任意几个数的之和例如：输入：x = 5；a[10] = {1,1,2,3,4,5}输出：5 = 5； 5 = 4 + 1； 5 = 3 + 2； 5 = 3 + 1 + 1；要求算法高效率同学说先排序，再递归，求出组合。各位的意见呢？

---

作者: 王培培    时间: 2013-8-16 10:11
贴一个不完整的吧，算是抛砖引玉……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.        ifst == 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 == False22.                   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]

---

欢迎光临 研发埠 (http://bbs.yanfabu.com/)

Powered by Discuz! X3.2