如何标记每一层可以选哪些元素，额外开一个visited数组
class Solution { public: int numTilePossibilities(string tiles) { sort(tiles.begin(),tiles.end()); vector<bool> visited(tiles.size()); dfs(tiles,visited); //for(auto s:res) cout<<s<<endl; return count-1; } int count = 0; //vector<string> res; //string path; void dfs(string tiles, vector<bool>& visited){ //res.push_back(path); count++; for(int i=0;i<tiles.size();i++){ if(i>0&&tiles[i]==tiles[i-1]&&!visited[i-1]) continue; if(!visited[i]){ visited[i] = true; //path+=tiles[i]; dfs(tiles,visited); //path.pop_back(); visited[i] = false; } } } };
更直接的方式是枚举每个字母用多少次，这种方法写起来更简单
class Solution { public: int dict[26] = {0}; int res = 0; int numTilePossibilities(string tiles) { for(auto c:tiles) dict[c-'A']++; dfs(); return res; } void dfs(){ for(int i=0;i<26;i++){ if(dict[i]!=0){ res++; dict[i]--; dfs(); dict[i]++; } } } };
