<p>There are <code>n</code> soldiers standing in a line. Each soldier is assigned a <strong>unique</strong> <code>rating</code> value.</p>

<p>You have to form a team of 3 soldiers amongst them under the following rules:</p>

<ul>
	<li>Choose 3 soldiers with index (<code>i</code>, <code>j</code>, <code>k</code>) with rating (<code>rating[i]</code>, <code>rating[j]</code>, <code>rating[k]</code>).</li>
	<li>A team is valid if: (<code>rating[i] &lt; rating[j] &lt; rating[k]</code>) or (<code>rating[i] &gt; rating[j] &gt; rating[k]</code>) where (<code>0 &lt;= i &lt; j &lt; k &lt; n</code>).</li>
</ul>

<p>Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).</p>

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

<pre>
<strong>Input:</strong> rating = [2,5,3,4,1]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 
</pre>

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

<pre>
<strong>Input:</strong> rating = [2,1,3]
<strong>Output:</strong> 0
<strong>Explanation:</strong> We can&#39;t form any team given the conditions.
</pre>

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

<pre>
<strong>Input:</strong> rating = [1,2,3,4]
<strong>Output:</strong> 4
</pre>

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

<ul>
	<li><code>n == rating.length</code></li>
	<li><code>3 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= rating[i] &lt;= 10<sup>5</sup></code></li>
	<li>All the integers in <code>rating</code> are <strong>unique</strong>.</li>
</ul>

class Solution {
public:
    unordered_map<string, int> memo;

    string createKey(int start, int count, int direction) {
        return to_string(start) + "," + to_string(count) + "," +
               to_string(direction);
    }
    int countTeamsHelper(const vector<int>& rating, int start, int count,
                         int direction) {
        if (count == 3) {
            return 1;
        }

        int n = rating.size();

        string key = createKey(start, count, direction);

        if (memo.find(key) != memo.end()) {
            return memo[key];
        }

        int totalTeams = 0;

        for (int i = start; i < n; ++i) {
            if (count == 0 ||
                (direction > 0 && rating[start - 1] < rating[i]) ||
                (direction < 0 && rating[start - 1] > rating[i])) {
                totalTeams +=
                    countTeamsHelper(rating, i + 1, count + 1, direction);
            }
        }

        memo[key] = totalTeams;
        return totalTeams;
    }

    int numTeams(vector<int>& rating) {
        int totalTeams = 0;

        for (int i = 0; i < rating.size(); ++i) {
            totalTeams += countTeamsHelper(rating, i + 1, 1, 1);  // Increasing
            totalTeams += countTeamsHelper(rating, i + 1, 1, -1); // Decreasing
        }

        return totalTeams;
    }
};
22216