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?
Given [1,2,3,4]
, k = 2
, target = 5
.
There are 2
solutions: [1,4]
and [2,3]
.
Return 2
.
public class Solution { /** * @param A: an integer array. * @param k: a positive integer (k <= length(A)) * @param target: a integer * @return an integer */ public int kSum(int A[], int k, int target) { // write your code here int[][][] result=new int[A.length+1][k+1][target+1]; for(int i=0;i<=A.length;i++) { result[i][0][0]=1; } for(int m=1;m<=A.length;m++) { for(int n=1;n<=k&n<=m;n++) { for(int l=1;l<=target;l++) { result[m][n][l]=0; if(A[m-1]<=l) { result[m][n][l]=result[m-1][n-1][l-A[m-1]]; } result[m][n][l]=result[m][n][l]+result[m-1][n][l]; } } } return result[A.length][k][target]; } }
原文:http://www.cnblogs.com/kittyamin/p/5055956.html