问一道题k Sum# JobHunting - 待字闺中
d*n
1 楼
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.
我用递归如下:
void helper(vector A,int k, int start,int target, int & ans) {
if (k < 0 || target < 0) return;
if (k == 0 && target == 0) {
ans++;
return;
}
for(int i = start; i <= A.size()-k; i++)
helper(A, k-1, i+1, target - A[i], ans);
}
int solutionKSum(vector A,int k,int target) {
int ans = 0;
helper(A, k, 0, target, ans);
return ans;
}
请问如何用DP降低复杂度?
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.
我用递归如下:
void helper(vector
if (k < 0 || target < 0) return;
if (k == 0 && target == 0) {
ans++;
return;
}
for(int i = start; i <= A.size()-k; i++)
helper(A, k-1, i+1, target - A[i], ans);
}
int solutionKSum(vector
int ans = 0;
helper(A, k, 0, target, ans);
return ans;
}
请问如何用DP降低复杂度?