<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:
        ans = 0
        answer = [] 
        for i in range(1,len(tiles)+1):
            drop = set(itertools.permutations(tiles,i))
            answer.append(drop)

            ans += len((drop))

        print(answer)

        return ans

        """
        PERMUTAION: order of piles does not matter! so "AB" != "BA"
        COMBINATION: order of piles does matter! "AB" == "BA"
        """

        # every time we can include it or not

#         ans = []  # answer
#         cur_combo = []

#         def dfs(i):
#             # base case
#             if i == len(tiles):
#                 ans.append(list(cur_combo))
#                 return

#             cur_combo.append(tiles[i]) # Decision TO include tiles[i]
#             print(cur_combo)
#             i += 1
#             dfs(i) # this recursive call will have an cur_combo given to it
        
#             cur_combo.pop() # Decision to NOT inlcude tiles[i]
            
#             i -= 1 # reset i back after changing it.

#             i += 1
#             dfs(i) # this recursive call will have an empty cur_combo given to it

#         dfs(0)
#         print(ans)
#         print(len(ans))
#         return len(ans)


# class Solution:
#     def numTilePossibilities(self, tiles: str) -> int:
#         ans = set()  # Use a set to avoid duplicates
#         cur_combo = []

#         def dfs(used):
#             if cur_combo:
#                 ans.add("".join(cur_combo))  # Add the current combination as a string

#             for i in range(len(tiles)):
#                 if used[i]:
#                     continue
#                 cur_combo.append(tiles[i])
#                 used[i] = True
#                 dfs(used)
#                 used[i] = False
#                 cur_combo.pop()

#         dfs([False] * len(tiles))
#         return len(ans)



20100