Java recursive backtracking solution, who can help to analyze the complexity?


  • 0
    S

    Just regular backtracking solution, nothing tricky than the classic backtracking problems like Subset or Combination Sum and so on. Just pay attention to the return condition.

    It seems O(n^2) time. I'm not sure. Who can help to analyze? Thanks in advance!

    UPDATE : It's definitely not O(n^2), this code calculate duplicate case many times. I think I need memorization somewhere to make it O(n^2)...

    public int lengthOfLIS(int[] nums) {
            if (nums.length == 0) return 0;
            int[] maxLen = new int[]{0};
            getMaxLen(nums, 0, maxLen, new ArrayList<Integer>());
            return maxLen[0];
        }
        
        public void getMaxLen(int[] nums, int startPos, int[] maxLen, List<Integer> tmp)
        {
            if (startPos == nums.length)
            {
                maxLen[0] = Math.max(tmp.size(), maxLen[0]);
                return;
            }
            
            // if there's no enough numbers behind current position, just return
            if (tmp.size() + nums.length - startPos < maxLen[0]) return;
    
                      
            int largerCnt = 0;  // a counter to counter how many numbers behind current position larger than current num
            for (int index = startPos; index < nums.length; index++)
            {
                if (tmp.size() == 0 || tmp.get(tmp.size() - 1) < nums[index])
                {
                    largerCnt++;
                    tmp.add(nums[index]);
                    getMaxLen(nums, index + 1, maxLen, tmp);
                    tmp.remove(tmp.size() - 1);
                }
            }
            
            // if no larger numbers behind current number, then the current number is the last one for the current sequence
            if (largerCnt == 0) maxLen[0] = Math.max(tmp.size(), maxLen[0]);
        }

  • 0
    Q

    Let's count all recursive calls. n + (n-1) + 2(n-2)+ 3(n-3) + ...
    All sums are 1 to n

    n+∑i(n-i) = n+∑ni-∑i^2 =n+n∑i-∑i^2 = n+n[n(n+1)/2]-( n^3/3 +n^2/2+n/6) = O(n^3)

    See

    [https://en.wikipedia.org/wiki/Summation][1]
    

Log in to reply
 

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