K Sum II(LintCode)

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

在这n个数里面找出K个数，使得这K个数的和等于目标数字，你需要找出所有满足要求的方案。

样例

给出[1,2,3,4]，k=2， target=5，返回 [[1,4],[2,3]]

DFS+backtracking

public List<List<Integer>> kSumII(int[] A, int k, int target) {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    if (A == null || A.length == 0) {
        return res;
    }

    List<Integer> current = new ArrayList<>();

    dfs(A,k,target,res,current,0);

    return res;
}

private void dfs(int[] A, int k, int target,List<List<Integer>> res,List<Integer> current,int start) {
        if(current.size() == k) {
            if(target == 0) {
                List<Integer> tmp = new ArrayList<>(current);
                res.add(tmp);
            }
            return;
        }

        for(int i=start;i<A.length;i++) {
            current.add(A[i]);
            dfs(A,k,target-A[i],res,current,i+1);
            current.remove(current.size()-1);
        }
}

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?

后面的优化主页君没有管。 F[0][0][0]表示在一个空集中找出0个数，target为0，则有1个解，就是什么也不挑嘛！ 其实应该这样写，也就是说，找0个数，目标为0，则一定是有1个解： if (j == 0 && t == 0) { 　　// select 0 number from i to the target: 0 　　D[i][j][t] = 1; }

1. 状态表达式：

D[i][j][t] = D[i - 1][j][t]; if (t - A[i - 1] >= 0) { D[i][j][t] += D[i - 1][j - 1][t - A[i - 1]]; }

意思就是：

（1）我们可以把当前A[i - 1]这个值包括进来，所以需要加上D[i - 1][j - 1][t - A[i - 1]]（前提是t - A[i - 1]要大于0）

（2）我们可以不选择A[i - 1]这个值，这种情况就是D[i - 1][j][t]，也就是说直接在前i-1个值里选择一些值加到target.

/**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
    public int  kSum1(int A[], int k, int target) {
        // write your code here
        if (target < 0) {
            return 0;
        }

        int len = A.length;

        int[][][] D = new int[len + 1][k + 1][target + 1];

        for (int i = 0; i <= len; i++) {
            for (int j = 0; j <= k; j++) {
                for (int t = 0; t <= target; t++) {
                    if (j == 0 && t == 0) {
                        // select 0 number from i to the target: 0
                        D[i][j][t] = 1;
                    } else if (!(i == 0 || j == 0 || t == 0)) {
                        D[i][j][t] = D[i - 1][j][t];
                        if (t - A[i - 1] >= 0) {
                            D[i][j][t] += D[i - 1][j - 1][t - A[i - 1]];
                        }
                    }
                }
            }
        }

        return D[len][k][target];
}

References

1 K Sum Solution