腾讯面试算法题：序列求和

腾讯面试算法题：序列求和

题目详情

给一个无重复的候选数字集合C和一个数字target，求和为target的序列，序列中的数都来自于集合C，序列为有序序列。

leetcode 与相关解答

* leetcode: https://leetcode.com/problems/combination-sum/description/
<https://leetcode.com/problems/combination-sum/description/>
* CSDN：https://blog.csdn.net/jmspan/article/details/51452235
<https://blog.csdn.net/jmspan/article/details/51452235>
分析

* 相当于有放回抽样问题，暴力搜索的复杂度为指数级
* 类比维特比算法，可以使用动态规划，将复杂度降低到， O(NK)
* 使用递归实现动态规划算法
* 确定递归的输入和输出，输入是target和C, 返回的是，寻找到的list的集合。
python实现
def find_child(target, C): """ input: target: a int number C: a list for
search return: """ ret = [] for child_idx in range(len(C)): child = C[child_idx]
if child == target: ret.append([child]) elif child<target: ret_list =
find_child(target-child, C)for child_list_temp in ret_list:
child_list_temp.append(child) ret.append(child_list_temp)else: pass return ret
if __name__ == "__main__": target = 8 C = [2,3, 5] ret = find_child(target, C)
print(ret)
输出
[[2,2,2,2],[3,3,2],[3,2,3],[2,3,3],[5,3],[3,5]]

• « 上一篇：服务器最大连接数问题
• » 下一篇：Linux删除文件后，发现磁盘空间没有释放-lsof