Recursive Solution get TLE


  • 0
    S

    I've tried recursion at my first attempt. It always gets TLE. I look into the run time and I think it is O(n!), which is not a linear time. Here is my code.

    public class Solution {
            List<List<Integer>> output = new ArrayList<List<Integer>>();
        	HashSet<List<Integer>> visited = new HashSet<List<Integer>>();
        	final static int pivot = 4;
            public List<List<Integer>> fourSum(int[] num, int target) {
                Arrays.sort(num);
                search(0,target,0,num, new ArrayList<Integer>());
                return output;
            }
            
            private void search(int sum, int target, int index, int[] num, List<Integer> lst){
                if(lst.size()==pivot){
                    if(sum == target)
                    	if(!visited.contains(lst)){
                    		visited.add(lst);
                    		output.add(lst);
                    	}
                    return;
                }
                if(sum + (pivot-lst.size())*num[num.length-1] < target){return;}
                if(sum + (pivot-lst.size())*num[index] > target){return;}
                for(int i = index;i <= num.length-(pivot-lst.size());i++){
                    if(sum + (pivot-lst.size())*num[i] > target){return;}
                    List<Integer> newlst = new ArrayList<Integer>(lst);
                    newlst.add(num[i]);
                    search(sum + num[i], target, i+1, num, newlst);
                }
                return;
            }
        }

  • 0
    L

    Hi, thank you for your code!
    Have you find a recursive version which is accepted finally. I want to try the recursive method too.


Log in to reply
 

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