首页 > 代码库 > LintCode-K Sum
LintCode-K Sum
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.
Analysis:
DP. d[i][j][v] means the way of selecting i elements from the first j elements so that their sum equals to k. Then we have:
d[i][j][v] = d[i-1][j-1][v-A[j-1]] + d[i][j-1][v]
It means two operations, select the jth element and not select the jth element.
Solution:
1 public class Solution { 2 /** 3 * @param A: an integer array. 4 * @param k: a positive integer (k <= length(A)) 5 * @param target: a integer 6 * @return an integer 7 */ 8 public int kSum(int A[], int k, int target) { 9 if (A.length<k) return 0;10 int[][][] d = new int[k+1][A.length+1][target+1];11 for (int i=1;i<=A.length;i++)12 if (A[i-1]<=target){13 for (int j=i;j<=A.length;j++)14 d[1][j][A[i-1]] = 1;15 }16 17 for (int i=2;i<=k;i++)18 for (int j=i;j<=A.length;j++)19 for (int v = 1; v<=target;v++){20 d[i][j][v]=0;21 if (j>i) d[i][j][v] += d[i][j-1][v];22 if (v>=A[j-1]) d[i][j][v] += d[i-1][j-1][v-A[j-1]];23 }24 25 return d[k][A.length][target];26 27 }28 }
LintCode-K Sum
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。