My solution generalized for kSums in JAVA


  • 36

    General Idea

    If you have already read and implement the 3sum and 4sum by using the sorting approach: reduce them into 2sum at the end, you might already got the feeling that, all ksum problem can be divided into two problems:

    1. 2sum Problem
    2. Reduce K sum problem to K – 1 sum Problem

    Therefore, the ideas is simple and straightforward. We could use recursive to solve this problem. Time complexity is O(N^(K-1)).

        public class Solution {
            int len = 0;
            public List<List<Integer>> fourSum(int[] nums, int target) {
                len = nums.length;
                Arrays.sort(nums);
                return kSum(nums, target, 4, 0);
            }
           private ArrayList<List<Integer>> kSum(int[] nums, int target, int k, int index) {
                ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
                if(index >= len) {
                    return res;
                }
                if(k == 2) {
                	int i = index, j = len - 1;
                	while(i < j) {
                        //find a pair
                	    if(target - nums[i] == nums[j]) {
                	    	List<Integer> temp = new ArrayList<>();
                        	temp.add(nums[i]);
                        	temp.add(target-nums[i]);
                            res.add(temp);
                            //skip duplication
                            while(i<j && nums[i]==nums[i+1]) i++;
                            while(i<j && nums[j-1]==nums[j]) j--;
                            i++;
                            j--;
                        //move left bound
                	    } else if (target - nums[i] > nums[j]) {
                	        i++;
                        //move right bound
                	    } else {
                	        j--;
                	    }
                	}
                } else{
                    for (int i = index; i < len - k + 1; i++) {
                        //use current number to reduce ksum into k-1sum
                        ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k-1, i+1);
                        if(temp != null){
                            //add previous results
                            for (List<Integer> t : temp) {
                                t.add(0, nums[i]);
                            }
                            res.addAll(temp);
                        }
                        while (i < len-1 && nums[i] == nums[i+1]) {
                            //skip duplicated numbers
                            i++;
                        }
                    }
                }
                return res;
            }
        }
    

  • 0
    X

    that`s really nice solution, especially this part at the end of each loop :

    while (i < len-1 && nums[i] == nums[i+1]) {
                        i++;
                    }
    

  • 0
    L

    Even though the run time performance is little bit slower than other post, I'd like to vote up here since the code is much easy to scale.:)


  • 0
    E

    I like this solution. other recursion solution is pretty mess but this one looks beautiful and clear.


  • 0
    B

    A slightly improved version removing some unnecessary code:)

    public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            return kSum(nums, 0, 4, target);
        }
        private List<List<Integer>> kSum (int[] nums, int start, int k, int target) {
            int len = nums.length;
            List<List<Integer>> res = new ArrayList<List<Integer>>();
            if(k == 2) { //two pointers from left and right
                int left = start, right = len - 1;
                while(left < right) {
                    int sum = nums[left] + nums[right];
                    if(sum == target) {
                        List<Integer> path = new ArrayList<Integer>();
                        path.add(nums[left]);
                        path.add(nums[right]);
                        res.add(path);
                        while(left < right && nums[left] == nums[left + 1]) left++;
                        while(left < right && nums[right] == nums[right - 1]) right--;
                        left++;
                        right--;
                    } else if (sum < target) { //move left
                        left++;
                    } else { //move right
                        right--;
                    }
                }
            } else {
                for(int i = start; i < len - (k - 1); i++) {
                    if(i > start && nums[i] == nums[i - 1]) continue;
                    List<List<Integer>> temp = kSum(nums, i + 1, k - 1, target - nums[i]);
                    for(List<Integer> t : temp) {
                       t.add(0, nums[i]);
                    }                    
                    res.addAll(temp);
                }
            }
            return res;
        }
    

Log in to reply
 

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