Generic nSum Java Solution beats 98%


  • 0
    public class Solution {
        
        // assume input array is sorted (can contain duplicates!)
        public List<List<Integer>> nSum(int[] nums, int startIdx, int n, int target) {
            ArrayList<List<Integer>> l = new ArrayList<List<Integer>>();
            
            if(n <= 0 || startIdx >= nums.length || startIdx+n > nums.length)
                return l;
            
            // Note: this is important, early prune the cases where the sum of first n > target
            int sum = 0;
            for(int i=0; i<n; i++)
                sum += nums[startIdx+i];
            if (sum>target)
                return l;
            
            // Note: this is important, early prune the cases where the sum of last n < target
            sum = 0;
            for(int i=nums.length-1; i>=nums.length-n; i--)
                sum += nums[i];
            if (sum<target)
                return l;
            
            if(n==1) {
                for(int i=startIdx; i<nums.length; i++) {
                    if(nums[i]==target) {
                        ArrayList<Integer> subL = new ArrayList<Integer>();
                        subL.add(nums[i]);
                        l.add(subL);
                        break;
                    }
                }
            } else {
                int startVal = nums[startIdx];
                int startCount = 1;
                for(int i=startIdx+1; i<nums.length; i++) {
                    if(nums[i]==startVal)
                        startCount++;
                    else
                        break;
                }
                for(int i=0; i<=startCount; i++) {
                    List<List<Integer>> ls = nSum(nums,startIdx+startCount,n-i,target-i*startVal);
                    for(List<Integer> postLs : ls) { // merge the lists
                        ArrayList<Integer> prefixLs = new ArrayList<Integer>();
                        for(int j=1; j<=i; j++) // add duplicates startVals first
                            prefixLs.add(startVal);
                        prefixLs.addAll(postLs);
                        l.add(prefixLs);
                    }
                }
                // Note: this is tricky, this handles the case the current target can consists of all duplicates values!
                if(startCount>=n && target-n*startVal==0) {
                    System.out.println("Triggered " + startVal);
                    ArrayList<Integer> prefixLs = new ArrayList<Integer>();
                    for(int j=1; j<=n; j++)
                        prefixLs.add(startVal);
                    l.add(prefixLs);
                }
            }
            return l;
        }
        
        public List<List<Integer>> fourSum(int[] nums, int target) {
            Arrays.sort(nums);
            return nSum(nums, 0, 4, target);
        }
    }

Log in to reply
 

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