k Sum II 90

Question

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

Find all possible k integers where their sum is target.

Example

Given [1,2,3,4], k = 2, target = 5. Return:

[ [1,4],

[2,3] ]

Solution

DFS递归求解。

代码如下：

public class Solution {
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return a list of lists of integer 
     */ 
    public ArrayList<ArrayList<Integer>> kSumII(int[] A, int k, int target) {
        // write your code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(A == null || A.length == 0){
            return result;
        }

        ArrayList<Integer> list = new ArrayList<Integer>();
        Arrays.sort(A);
        helper(result, list, A, k, target, 0);

        return result;
    }

    private void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> list, int[] A, int k, int target, int pos){

        if(k == 0 && target == 0){
            result.add(new ArrayList<Integer>(list));
            return;
        }

        if(k > 0 && target > 0){
            for(int i = pos; i < A.length; i++){
                if(A[i] > target){
                    return;
                }
                list.add(A[i]);
                helper(result, list, A, k - 1, target - A[i], i + 1);
                list.remove(list.size() - 1);
            }
        }
    }
}