排列树的构造：
无重复画法：一条线前面出现的不再出现。
有重复画法：一条线前面出现的不再出现，如果仅仅只是相似可以出现；兄弟不能相似。
- 目标函数是：cnt == 总元素个数
- 分支策略是全遍历，不过存在约束
- 关键在于记录当前结点所选择的数，下一层别选了，换到兄弟结点之前要回溯。这里防的是儿子，建议这里的记录结构要么是全局性的，要么是参数性的。
- 如果存在重复元素的话，就比较麻烦一点：也是要记录当前结点所选择的数，但是换到兄弟结点之前不用回溯，因为防的就是兄弟。所以这里的记录结构是局部性的。
- 最后，还有一点要强调，长得一模一样的兄弟不允许（1223和1223重了），所以判断的依据在于值；同一个人不能多次出现在一条辈分线上（1223排序，你不能12232），所以判断的依据在于编号，长得像的人可以在同一条辈分线上（1223可以）。
#include<bits/stdc++.h>
using namespace std;
string str;
int n;
int sign_for_son[220];
void dfs(int cnt, string result)
{
if(cnt > n)
{
cout << result << endl;
return;
}
int sign_for_bro[220] = {0};
for(int i = 0; i < n; i++)
{
if(sign_for_son[i]) continue;
if(sign_for_bro[str[i]]) continue;
sign_for_son[i] = 1;
string temp = result;
result += str[i];
dfs(cnt+1, result);
result = temp;
sign_for_son[i] = 0;
sign_for_bro[str[i]] = 1;
}
return;
}
int main()
{
cin >> str;
n = str.size();
dfs(1, "");
return 0;
}组合树（这里我默认所有的元素都不相同，即便事实相同）的构造：
如果不限制数量，那么组合数就成了子集树：
1，0子集树：
画法：01法，每层考虑一个数
- 目标函数是：cnt == 总元素个数
- 分支策略是固定不变的：取，不取
- 不需要记录
#include<bits/stdc++.h>
using namespace std;
string str;
int n;
void dfs(int cnt, string result)
{
if(cnt > n)
{
cout << result << endl;
return;
}
dfs(cnt+1, result);
string temp = result;
result += str[cnt-1];
dfs(cnt+1, result);
result = temp;
return;
}
int main()
{
cin >> str;
n = str.size();
dfs(1, "");
return 0;
}如果限制数量：
画法：从小到大排序来遍历；儿子必须比父亲大（编号大值大一样）
- 目标函数是：cnt == 限制数量
- 分支策略也是全遍历，但与排列树存在不同的约束
- 这里不是记录，而是需要排列：当我们按照从小到大来遍历（先sort），可以保证前面的兄弟小于当前的，当我们又保证儿子比父亲大（i = last+1），那么儿子不会和叔叔伯伯雷同，也就不会出现12、21的重复了。
#include<bits/stdc++.h>
using namespace std;
int num[220];
int n, m;
void dfs(int cnt, int last, string result)
{
if(cnt > m)
{
if(result.size() == m) cout << result << endl;
return;
}
for(int i = last+1; i <= n; i++)
{
string temp = result;
result += num[i] + '0';
dfs(cnt+1, i, result);
result = temp;
}
return;
}
int main()
{
cin >> n;
for(int i = 1; i <= n; i++) cin >> num[i];
cin >> m;
sort(num+1, num+n+1);
dfs(1, 0, "");
return 0;
}
