Original Submission

class DPState:
    def __init__(self):
        # number which end at this
        self.num_two_length = 0
        self.num_arithmetic = 0

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        N = len(nums)
        dp = [{} for _ in range(N)]

        ans = 0
        for i in range(N):
            for j in range(i + 1, N):
                delta = nums[j] - nums[i]
                if delta == 0:  # We handle these below
                    continue

                if delta not in dp[j]:
                    dp[j][delta] = DPState()

                dp[j][delta].num_two_length += 1
                if delta not in dp[i]:
                    continue

                to_add = dp[i][delta].num_two_length + dp[i][delta].num_arithmetic
                dp[j][delta].num_arithmetic += to_add
                ans += to_add

        # Handle duplicates
        for k, cnt in Counter(nums).items():
            if cnt < 3:
                continue

            ans += (
                2 ** cnt
                - 1  # Remove nothing choice
                - cnt  # Remove single element choice
                - cnt * (cnt - 1) // 2  # Remove double element choice.
            )

        return ans