K数和

题目：

给定n个不同的正整数，整数k（k < = n）以及一个目标数字。　

在这n个数里面找出K个数，使得这K个数的和等于目标数字，求问有多少种方案？

您在真实的面试中是否遇到过这个题？ 

Yes

样例

给出[1,2,3,4]，k=2， target=5，[1,4] and [2,3]是2个符合要求的方案

题目地址

解题思路，看到这道题，很明显就是使用动态规划的办法，是01背包变种，我们按照01背包的思路，把原来的二维数组改成三维数组即可：f[i][k][target] = f[i-1][k][target] + f[i-1][k-1][target-arr[i]]；我们总结这个公式可以发现，全局和第一维i是没有逻辑上的关系的，此时我们可以把其优化为二维数组，代码如下：

package lintcode;

import java.util.Scanner;

/**
 * Created by Taoyongpan on 2017/11/15.
 * 给定 n 个不同的正整数，整数 k（k < = n）以及一个目标数字。在这 n 个数里面找出 k 个数，
 * 使得这 k 个数的和等于目标数字，写一个函数实现找到不同的方案的数量。
 */
public class SumOfK {

    //随机产生数组
    public static int[] generateRandomArray(int maxSize, int maxValue){
        if (maxSize<=0){
            return null;
        }
        int[] arr = new int[(int) ((maxSize+1)*Math.random())];
        for (int i = 0 ; i<arr.length;i++){
            arr[i] = (int) ((maxValue+1)*Math.random());
        }
        return arr;
    }

    public static int sum(int[] arr,int k,int target){
        int n = arr.length;
        int num = 0 ;

        if (k<0||k>n){
            return num;
        }
        int[][] f = new int[k+1][target+1];
        f[0][0] = 1;
        //f[i][k][target] = f[i-1][k][target] + f[i-1][k-1][target-arr[i]]
        for (int i = 0; i < n; i++){
            for (int j = k ; j >= 1;j--){
                for (int s = target ; s >= arr[i] ; s--){
                    f[j][s] = f[j][s]+f[j-1][s-arr[i]];
                }
            }
        }
        return f[k][target];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        while (sc.hasNext()){
            int maxSize = 10;//随机产生数组的最大规格
            int maxValve = 50 ;//随机数组的最大值
            int[] arr = {1,2,3,4};
            int k = sc.nextInt();
            int target = sc.nextInt();
            System.out.println(sum(arr,k,target));

        }
    }
}