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.
    /* DP的方法
     * dp[i][j][t]表示前i个元素里面取j个元素之和为t有多少个方案
     * 初始化：ksum[i][0][0] =1(i: 0 ~ n)，即前i个元素里面取0个元素使其和为0的方法只有1种，那就是什么都不取
     * 意思就是：
     * （1）我们可以把当前A[i - 1]这个值包括进来，所以需要加上dp[i - 1][j - 1][t - A[i - 1]]（前提是t - A[i - 1]要大于0）
     * （2）我们可以不选择A[i - 1]这个值，这种情况就是dp[i - 1][j][t]，也就是说直接在前i-1个值里选择一些值加到target.
     */
    public int  kSum(int A[], int k, int target) {
        int n = A.length;
        int[][][] f = new int[n + 1][k + 1][target + 1];
        for (int i = 0; i < n + 1; i++) {
            f[i][0][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k && j <= i; j++) {
                for (int t = 1; t <= target; t++) {
                    f[i][j][t] = 0;
                    if (t >= A[i - 1]) {
                        f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
                    }
                    f[i][j][t] += f[i - 1][j][t];
                } // for t
            } // for j
        } // for i
        return f[n][k][target];
    }

    // 优化space
滚动数组优化空间复杂度。
prev[j][x]表示从A[0]到A[i-1]，取j个数，使这些数的和为x。
current[j][x]表示从A[0]到A[i]，取j个数，使这些数的和为x。

在第i个位置，current[j][x]考虑取A[i]的情况和不取A[i]的情况：
取A[i]：prev[j-1][x-A[i]] ：前i-1个数取j-1个，和为x-A[i]，加上这次取A[i]，一共取了j个和为x
不取A[i]：prev[j][x]：前i-1个数取j个，和为x

所以有：current[j][x] = prev[j-1][x-A[i]]+prev[j][x]
    public int kSum(int[] A, int k, int target) {
        // write your code here
        int[][] prev = new int[k+1][target+1];
        prev[0][0] = 1;
        for(int i = 0; i < A.length; i++) {
            int[][] current = new int[k+1][target+1];
            current[0][0] = 1;
            for(int j = 1; j <= k; j++) {
                for(int x = 0; x <= target; x++) {
                    current[j][x] = prev[j][x];
                    if(x>=A[i]) {
                        current[j][x] += prev[j-1][x-A[i]];
                    }
                }
            }
            prev = current;
        }
        return prev[k][target];
    }

    // 方法2: backtracking，time: O(2^n)
    static List<Integer> result = new ArrayList<Integer>();
    static boolean flag = false;

    public static List<Integer> kSum3(int A[], int k, int target) {
        backtrack(result, A, k, target, 0);
        return result;
    }

    public static void backtrack(List<Integer> path, int[] A, int k, int remain, int index) {
        if (path.size() == k) {
            if (remain == 0) flag = true;
            return;
        }
        for (int i = index; i < A.length; i++) {
            path.add(A[i]);
            backtrack(path, A, k, remain - A[i], i + 1);
            if (flag) break;
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 6, 4, 7, 4, 3, 2, 5};
        System.out.println(kSum3(arr, 2, 6));
    }