Problem statement

https://binarysearch.com/problems/Arithmetic-Subsequences/

Solution

Equal to Leetcode 0446. Arithmetic Slices II - Subsequence.

Complexity

Time and space is O(n^2).

Code

class Solution:
    def solve(self, A):
        total, n = 0, len(A)
        dp = [Counter() for item in A]
        for i in range(n):
            for j in range(i):
                dp[i][A[i] - A[j]] += (dp[j][A[i] - A[j]] + 1)      
            total += sum(dp[i].values())
          
        return total - (n-1)*n//2