My Backtracing + DFS method has a TLE


  • 0
    S
    public List<List<Integer>> threeSum(int[] nums) {
         List<List<Integer>> result = new ArrayList();
         List<Integer> path = new ArrayList();
         
         if(nums==null || nums.length == 0){
             return result;
         }
         
         backtracing(result, path, 3, 0, nums);
         
         return result;
         
        }
        
        public void backtracing(List<List<Integer>> result, List<Integer> path, int k, int current, int[] nums){
            if(nums.length == 0 || nums == null){
                return;
            }
            
            if(k==0){
                if(path.get(0)+path.get(1)+path.get(2)==0){
                    result.add(new ArrayList(path));
                }
                return;
            }
            
            for(int i=current; i<nums.length; i++){
                path.add(nums[i]);
                backtracing(result, path, k-1, i+1, nums);
                path.remove(path.size()-1);
                while(i<nums.length-1 && nums[i] == nums[i+1]){
                    i++;
                }
            }
            
        }
    

    Would you please help me to find out why it gives me a TLE??


  • 0
    S

    It works when I firstly sort the array, but why?


Log in to reply
 

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