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

• 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++;
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]);
}``````

• 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]
``````

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