Welcome to LeetCode Discuss.  Please read the FAQ to help yourself making the best use of Discuss.
Ask a Question
Back to Problem

Welcome to LeetCode Discuss.

This is a place to ask questions related to only OJ problems.

Please read the FAQ to help yourself making the best use of Discuss.

HELP: Getting "Output Limit Exceeded"

0 votes
29 views

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;
}
asked Nov 18 in Combination Sum by simpleCoder (180 points)
reshown Nov 18 by simpleCoder

Please log in or register to answer this question.


...