题目
Given n distinct positive integers, integer k (k <= n) and a number target.
Find k numbers where sum is target. Calculate how many solutions there are?
Example
Given [1,2,3,4], k=2, target=5. There are 2 solutions:
[1,4] and [2,3], return 2.
Tags Expand
LintCode Copyright Dynamic Programming
解题思路
思路一: 迭代,开始时依次选择一个点,然后根据新的target值和新的数组,选择k-1个数,思路直接简单。但是存在重复计算。该算法复杂度为 Nk{N^k } ,指数递增,所以在lintcode中就计算超时了......
阅读全文