HELP: Getting "Output Limit Exceeded"


  • 1
    S

    Edit: I made a silly error and found it and fixed the problem:
    In my helper() function, I forgot to change my "i" to start at "startIndex"
    Anyway, I am going to leave this here, so others can learn from and comment on my code.
    This is working code, and passes the OJ

    My approach is to sort the candidates, then remove duplicates, and then pass it on to a helper() function which recursively adds only the current and and higher indices to an arrayList and keeps track of the sum.

    I tested my code on my computer and I cannot see any additional outputs, but the OJ is giving me "Output Limit Exceeded.

    Here is my code:

    public static void helper(ArrayList<ArrayList<Integer>> aal, ArrayList<Integer> alTemp, 
                              int[] candidates, int target, int startIndex) {
        if(target == 0) {
            ArrayList<Integer> al = new ArrayList<Integer>();
            al.addAll(alTemp);
            aal.add(al);
            return;
        } 
        
        if(target < 0)
            return;
        
        for(int i = startIndex; i < candidates.length; i++) {
            alTemp.add(candidates[i]);
            helper(aal, alTemp, candidates, target - candidates[i], i);
            alTemp.remove(alTemp.size()-1);
        }
    }
    
    public static int[] removeDuplicates(int[] arr) {
        if(arr.length <= 1)
            return arr;
    
        int dropIndex = 0;
        int i = 1;
        while(i < arr.length) {
            if(arr[dropIndex] != arr[i]) {
                dropIndex++;
                arr[dropIndex] = arr[i];
            } 
            i++;       
        }
    
        int[] retArr = new int[dropIndex+1];
        while(dropIndex >= 0) {
            retArr[dropIndex] = arr[dropIndex];
            dropIndex--;
        }
    
        return retArr;
    }
    
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        ArrayList<ArrayList<Integer>> aal = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> alTemp = new ArrayList<Integer>();
        
        Arrays.sort(candidates);
        int[] newCandidates = removeDuplicates(candidates);
        
        helper(aal, alTemp, newCandidates, target, 0);
        
        return aal;
    }

Log in to reply
 

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