<p>Given an integer array <code>nums</code>, return <em>the number of all the <strong>arithmetic subsequences</strong> of</em> <code>nums</code>.</p>

<p>A sequence of numbers is called arithmetic if it consists of <strong>at least three elements</strong> and if the difference between any two consecutive elements is the same.</p>

<ul>
	<li>For example, <code>[1, 3, 5, 7, 9]</code>, <code>[7, 7, 7, 7]</code>, and <code>[3, -1, -5, -9]</code> are arithmetic sequences.</li>
	<li>For example, <code>[1, 1, 2, 5, 7]</code> is not an arithmetic sequence.</li>
</ul>

<p>A <strong>subsequence</strong> of an array is a sequence that can be formed by removing some elements (possibly none) of the array.</p>

<ul>
	<li>For example, <code>[2,5,10]</code> is a subsequence of <code>[1,2,1,<strong><u>2</u></strong>,4,1,<u><strong>5</strong></u>,<u><strong>10</strong></u>]</code>.</li>
</ul>

<p>The test cases are generated so that the answer fits in <strong>32-bit</strong> integer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,4,6,8,10]
<strong>Output:</strong> 7
<strong>Explanation:</strong> All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [7,7,7,7,7]
<strong>Output:</strong> 16
<strong>Explanation:</strong> Any subsequence of this array is arithmetic.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1&nbsp; &lt;= nums.length &lt;= 1000</code></li>
	<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution {
public:
   int nCr(int N, int r)
{
    int res = 0;
    if (r == 0) {
        return 1;
    }
    else {
        res = nCr(N, r - 1)
              * (N - r + 1) / r;
    }
    return res;
}
    void solve(vector<int>& nums,map<pair<int,int>,int>&m,int &ans)
    {

        // Isme abhi nCr wali cheez smjh nhi aa rhi
        // int n = nums.size();
        // for(int i=1;i<n;i++)
        // {
        //     for(int j=i-1;j>=0;j--)
        //     {
        //         int diff = nums[i]-nums[j];

        //         if(!m.empty())
        //         {
        //             auto it = m.upper_bound({j,diff});

        //             if(it==m.begin())
        //             {
        //                 m[{i,diff}]++;
        //                 continue;
        //             }
        //             --it;

        //             int ind = it->first.first;
        //             int diff1 = it->first.second;
        //             int len = it->second;

        //             if(diff1==diff and ind<i)
        //             {
        //                 m.erase({ind,diff1});
        //                 m[{i,diff}]= len+1;
        //                 if(m[{i,diff}]>=2)
        //                 {
        //                     ans+=
        //                 }

        //             }
        //             else
        //             {
        //                 m[{i,diff}]++;
        //             }
        //         }
        //         else
        //         {
        //             m[{i,diff}]++;
        //         }
        //     }
        // }
        // cout<<endl;
        // for(auto it : m)
        // {
        //     cout<<it.first.first<<" "<<it.first.second<<endl;
        //     cout<<it.second<<endl;
        // }


        int n = nums.size();
        unordered_map<long long,long long> dp[n+1];
        for(int i=1;i<n;i++)
        {
            for(int j=i-1;j>=0;j--)
            {
                long long int diff =(long long int) nums[i]-(long long int)nums[j];
                long long int cnt = 1;
                if(dp[j].find(diff)!=dp[j].end())
                {
                   cnt = dp[j][diff];
                   dp[i][diff]+= cnt;
                   ans += cnt;
                }

                dp[i][diff] += 1 ;
            }
        }
    }
    int numberOfArithmeticSlices(vector<int>& nums) {
        map<pair<int,int>,int>m;
        int ans=0;
        solve(nums,m,ans);
        return ans;
    }
};
145354