k Sum II

Given n unique integers, number k (1<=k<=n) and target.

Find all possible k integers where their sum is target.

Solution:

We solve this problem by using depth first search. In each level of dfs, two cases are considered

1. current number is included in the k-sum
2. current number is not included in the k-sum

Code:

public class Solution {

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

    private void dfs(int k, int target, int[] A, int index, 
                    ArrayList<Integer> path, 
                    ArrayList<ArrayList<Integer>> res) {
        if (k == 0 && target == 0) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (k < 0 || target < 0 || index < 0) {
            return;
        }
        dfs(k, target, A, index - 1, path, res);
        path.add(A[index]);
        dfs(k - 1, target - A[index], A, index - 1, path, res);
        path.remove(path.size() - 1);
    }
}