手稿_V1.045
需积分: 0 68 浏览量
2022-08-03
12:43:51
上传
评论
收藏 175KB PDF 举报
分析:
方法一:回溯法,由于要去重,需要把原始数组进行排序,然后记录下递归调用helper的次数即可(注意
去掉空集).
这里与090_子集Ⅱ的处理不一样， 与 非同一组合，我们需要用 数组来做标
记.
方法一:C++_回溯法
/*
你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字
母序列的数目。
示例 1：
输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。
示例 2：
输入："AAABBC"
输出：188
提示：
1 <= tiles.length <= 7
tiles 由大写英文字母组成
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/letter-tile-possibilities
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution
{
private:
void helper( int& ret_val ,
vector<int>& vi ,
vector<int>& visited
)
{
ret_val++;
for (int i = 0; i < vi.size();i++)
{
if (visited[i] == 1)
{
continue;
}
if( i > 0
&& vi[i] == vi[i - 1]
&& visited[i-1] == 0
)
{
continue;
}
visited[i] = 1;
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
评论0