题目描述：
一套活字字模tiles，每个字模上都刻有一个字母tiles[i]。返回可以印出的非空字母序列的数目。存在重复字模，但是每个字模只能使用一次。
数据范围： $1\le tiles.length \le 7$
题解：
类似全排列问题。排列问题搜索树需要对每一个 tiles[i] 创建分支，排列问题分支数比较多。组合问题需要对 tiles[i]创建选与不选分支，固定两个分支。
但是这个问题是部分排列，不需要搜索到叶子结点再计数，需要对每个节点计数，除去根节点。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
int ans = 0;
int n;
vector<bool> vis;
void dfs(int step, string &s)
{
++ans;
for (int i = 0; i < n; ++i)
{
if (vis[i])
continue;
if (i > 0 && s[i] == s[i - 1] && !vis[i - 1])
continue;
vis[i] = true;
dfs(i + 1, s);
vis[i] = false;
}
}
int numTilePossibilities(string tiles)
{
n = tiles.size();
vis.resize(n, false);
sort(tiles.begin(), tiles.end());
dfs(0, tiles);
return ans - 1;
}
};
|
