<p>You have <code>n</code>&nbsp;&nbsp;<code>tiles</code>, where each tile has one letter <code>tiles[i]</code> printed on it.</p>

<p>Return <em>the number of possible non-empty sequences of letters</em> you can make using the letters printed on those <code>tiles</code>.</p>

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

<pre>
<strong>Input:</strong> tiles = &quot;AAB&quot;
<strong>Output:</strong> 8
<strong>Explanation: </strong>The possible sequences are &quot;A&quot;, &quot;B&quot;, &quot;AA&quot;, &quot;AB&quot;, &quot;BA&quot;, &quot;AAB&quot;, &quot;ABA&quot;, &quot;BAA&quot;.
</pre>

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

<pre>
<strong>Input:</strong> tiles = &quot;AAABBC&quot;
<strong>Output:</strong> 188
</pre>

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

<pre>
<strong>Input:</strong> tiles = &quot;V&quot;
<strong>Output:</strong> 1
</pre>

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

<ul>
	<li><code>1 &lt;= tiles.length &lt;= 7</code></li>
	<li><code>tiles</code> consists of uppercase English letters.</li>
</ul>

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        '''
        Assumptions and Insights:
            - Can we assume we'll always have a non-empty array of tiles?
                - Yes, at least one.
            - Can assume the characters will always be uppercase and strictly the English alphabet?
                - Yes.

            - Duplicates are possible in tiles recieved.
            - Input: A string of chars
            - Output: Return the number of unique permutations
            
            Test/Edge cases:
                - Long and short strings of the same char, should return 1
                - Long and short strings of the same 2 characters, should return 2
                - Normal test cases: AAB, AAABBC, V
        
        Brainstorm:
            Example 1: In: "AAB" ; Out: 8 ; Explaination: "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"

                AAB, permutations: {'A','AA','AAB', 'AB', 'ABA', 'B', 'BA', 'BAA'}
                  ^
                current: '', options: 'AAB'
                                       ├---current: 'A', options: 'AB'
                                       |                            ├---current: 'AA', options: 'B'
                                       |                            |                            ├---current: 'AAB', options: ''
                                       |                            |
                                       |                            ├---current: 'AB', options: 'A'
                                       |                                                         ├---current: 'ABA', options: ''                          
                                       |
                                       |---current: 'B', options: 'AA'
                                                                    |
                                                                    |
                                                                    ├--- current: 'BA', options: 'A'
                                                                                                  |
                                                                                                  |
                                                                                                  ├--- current: 'BAA', options: ''
    
            !! Check if 'BA' === 'AB' for a set !!
            Algorithm 1: Find all permutations and store in a set to prevent duplicates.

            func recursiveHelper(current_permutaion, tiles, idx, unique_permutations)
                Base case: 
                    if tiles length is 0, we return out of the function
                Recursive case:
                    We add every current permutation as long as it doesn't already exist in the current set of permutations
                    Leave breadcrumb, add the latest tile to the back of the current permutation
                    Continue the recursion w/ the current permutaion

                    Pick up breadcrumb, pop the latest added tile from the back of the current permutation
                    Continue the recursion w/ the current permutaion

            return the length of the set of permutations

            Runtime: O(n * 2^n) where n is the number of tiles in the input and we're doing an n operation at every call frame, 
                joining the array into a string, and the 2 comes from how many time we branch out at every call frame.
            Space: O(2^n) since we're holding 2^n permutatinon in the set
        '''
        def recursiveHelper(current_permutaion, tiles, unique_permutations):
            if len(tiles) == 0:
                return
            
            for i in range(len(tiles)):
                current_permutation.append(tiles[i])
                unique_permutations.add(''.join(current_permutation))
                recursiveHelper(current_permutation, tiles[:i] + tiles[i + 1:], unique_permutations)

                current_permutation.pop()
                recursiveHelper(current_permutation, tiles[:i] + tiles[i + 1:], unique_permutations)

        unique_permutations = set()
        current_permutation = []

        recursiveHelper(current_permutation, tiles, unique_permutations)

        return len(unique_permutations)


18300