KSum

题目描述

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

解题方法

/*O(K^n)*/
    public int kSum(int[] A, int k, int target) {
        if(A == null || A.length < k){ return 0;}

        Arrays.sort(A);
        int[] cnt = new int[1];
        KSum(A, k, target, 0, A.length - 1, cnt);
        System.out.println(cnt[0]);
        return cnt[0];
    }

    private void KSum(int[] A, int k, int target, int start, int end, int[] cnt){
        //termination
        if(k ==0 || A == null || A.length == 0 || start > end){ return;}

        if(k == 1){
            for(int i = start; i <= end; i++){
                if(A[i] == target){
                    cnt[0] += 1;
                }
            }
            return;
        }

        if(k == 2){//Using binary search
            int left = start;
            int right = end;
            while(left < right){
                int sum = A[left] + A[right];
                if(sum == target){
                    cnt[0] += 1;
                    left++;
                    right--;
                    //avoid duplicate num
                    while(left < right && A[left] == A[left - 1]){
                        left++;
                    }
                    while(left < right && A[right] == A[right + 1]){
                        right--;
                    }
                }else if(sum < target){
                    left++;
                }else{
                    right--;
                }
            }
            return;
        }

        //heuristic 
        if(k * A[start] > target || k * A[end] < target){ return;}

        for(int i = start; i <= end - k + 1; i++){
            if(i > start && A[i] == A[i - 1]){ continue;}
            if(k * A[i] < target){
                KSum(A, k - 1, target - A[i], i + 1, end, cnt);
            }
        }
    }