<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{
public:
void  rec(string par,set<vector<char>>& fs,int ind,vector<char>& cur,int n){
        
        fs.insert(cur); 
        for(int i=ind;i<n;i++){
            cur.push_back(par[i]);
            rec(par,fs,i+1,cur,n);
            cur.pop_back();
        }
    }
int fact[8] = { 1, 1, 2, 6, 24, 120, 720, 5040 };
unordered_set<string> st;
int uniquePerms(string& s) {
  int cnt[26] = {};
  for (auto ch : s) ++cnt[ch - 'A'];
  auto res = fact[s.size()];
  for (auto n : cnt) res /= fact[n];
  return res;
}
int dfs(string& s, string seq = "", int pos = 0) {
  if (pos >= s.size()) {
    if(seq==""){
        cout<<"e";
    }
    cout<<seq<<"\n";
    return st.insert(seq).second ? uniquePerms(seq) : 0;
  }
  return dfs(s, seq, pos + 1) + dfs(s, seq + s[pos], pos + 1);
}
int numTilePossibilities(string tiles) {
  sort(begin(tiles), end(tiles));
//   unordered_set<string> zet;
//   zet.insert("ab");
//   cout<<zet.insert("ba").second;
  set<vector<char>> fs;
  vector<char> cur;
  rec(tiles,fs,0,cur,tiles.length());
  for(const auto& vec: fs){
        for(int i=0;i<vec.size();i++){
                cout<<vec[i]<<" ";
            }
            cout<<"\n";
        }
  return dfs(tiles) - 1;
}
};
//     void perm(string par,vector<char>& crr,unordered_map<int,bool>& map,int ind,int n){
//         if(crr.size()==n){
//             return;
//         }

//     }

    // void  rec(string par,set<vector<char>>& fs,int ind,vector<char>& cur,int n){
        
    //     fs.insert(cur); 
    //     for(int i=ind;i<n;i++){
    //         cur.push_back(par[i]);
    //         rec(par,fs,i+1,cur,n);
    //         cur.pop_back();
    //     }
    // }
//     int fac(int n){
//         int f=1;
//         while(n>1){
//             f=f*n;
//             n--;
//         }
//         return f;
//     }
//     int count(const vector<char>& vec){
//         unordered_map<int,int> zmap;
//         for(int i=0;i<vec.size();i++){
//             zmap[vec[i]]++;
//         }
//         int num=fac(vec.size());
//         int den=1;
//         for(const auto& pair: zmap){
//             den*=fac(pair.second);
//         }
//         return num/den;
//     }
//     void dfs(map<int,int>& zmap,string tiles,int n,string& crr){
//         if(crr.length()==n){
//             return;
//         }
//         for(int i=0;i<tiles.length();i++){
//             if(zmap[i]==0){
//                 crr.push_back(tiles[i]);
//                 zmap[i]=1;
//                 dfs(ans,zmap,tiles,tiles.size(),crr);
//                 zmap[i]--;
//                 crr.pop_back();
                
//             }
//         }
//     }
//     int numTilePossibilities(string tiles){
        
//         set<vector<char>> fs;
//         set<string> ans;
//         string crr;
//         map<int,int> zmap;
//         dfs(ans,zmap,tiles,tiles.size(),crr);
//         return ans.size();

//         // rec(tiles,fs,0,cur,tiles.length());
//         // for(const auto& vec: fs){
//         //     for(int i=0;i<vec.size();i++){
//         //         cout<<vec[i]<<" ";
//         //     }
//         //     cout<<"\n";
//         // }
//         // int ans=0;
//         // for(const auto& vec: fs){
//         //     ans+=count(vec);  
//         // }
//         // return ans-1;
//     }
// };


11894