Once for all, solve Kth Sum Smaller problem


  • -1
    J
    public int threeSumSmaller(int[] nums, int target) {
        if(nums.length < 3) return 0;
        
        Arrays.sort(nums);
        return kSumSmaller(nums, 0, target, 3);
    }
    
    int kSumSmaller(int[] nums, int start, int target, int k) {
        if(k == 0) return target > 0 ? 1 : 0;
        
        int count = 0;
        for(int i = start; i < nums.length - k +1; ++i) {
            int n = kSumSmaller(nums, i+1, target - nums[i], k-1);
            if(n >0) count += n;
            else break;
        }
        return count;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.