Simple Java Solution for 4 sum, 3 sum, 2 sum, any sum...


  • 4
    C

    Any improvement is welcome.
    Updated: recursive stop at twoSum. Time Complexity of kSum is max( O(n^(k-1)), O(nlogn)).

    public class Solution {
        private List<List<Integer>> nSum(int[] nums, int start, int n, int target){
            List<List<Integer>> result = new LinkedList<>();
            // target is too small or too large so that there won't be solutions.
            if (target < nums[start]*n || target > nums[nums.length - 1]*n){
                return result;
            }
            
            for (int i = start, end = nums.length - n + 1; i < end; ++i){
                // avoid duplicated solutions
                if (i > start && nums[i - 1] == nums[i]){
                    continue;
                }
    
                if (n == 2){
                    int required = target - nums[i];
                    
                    while(nums[end] > required){
                        end--;
                    }
                    if (nums[end] < required){
                        continue;
                    }
                    if (i >= end){
                        break;
                    }
                    
                    // duplicated solution
                    if (end + 1 < nums.length && nums[end+1] == nums[end]){
                        continue;
                    }
                    
                    // get two sum
                    result.add(new LinkedList<Integer>(Arrays.asList(nums[i], nums[end])));
                    continue;
                }
                
                for (List<Integer> list : nSum(nums, i + 1, n - 1, target - nums[i])){
                    list.add(nums[i]);
                    result.add(list);
                }
                
            }
            return result;
        }
        
        public List<List<Integer>> fourSum(int[] nums, int target) {
            if (nums.length == 0){
                return Arrays.asList();
            }
            Arrays.sort(nums);
            return nSum(nums, 0, 4, target);
        }
    }
    

  • 0
    R

    thanks your for this brilliant answer.


  • 0
    M

    Actually, it's just backtracking. Maybe kind of solution, but the time complexity could be reduced based on the truth that 4 numbers sum.
    Backtracking here, is just brute force I think.


  • 0
    C

    @MrYy Thanks for the comment. Code updated.


  • 0
    C

    said in Simple Java Solution for 4 sum, 3 sum, 2 sum, any sum...:

    for (int i = start, end = nums.length - n + 1; i < end; ++i)
    why end is from nums.length - n + 1, what does this mean?


  • 0
    C

    @Chaofb You don't need to look for a solution for nSum in an array smaller than n.


Log in to reply
 

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