B3621 DFS 元组类
signed main() { cin >> n >> k; dfs(0); return 0; }
！！！错误：
void dfs(int i){//已经放了i个数
if(i == n){//若放满i元
for(int j=1;j<=n;j++){
cout<<a[j]<<' ';
}
cout<<'\n';
return;
}
else {
//若没放满，则继续放下一元
for(int j=1;j<=k;j++){
i++;
a[i]=j;
dfs(i); //!!!dfs后没有回溯，会导致i一直++
}
}
}
解决方案1：
void dfs(int i){//已经放了i个数
if(i == n){//若放满i元
for(int j=1;j<=n;j++){
cout<<a[j]<<' ';
}
cout<<'\n';
return;
}
else {
//若没放满，则继续放下一元
for(int j=1;j<=k;j++){
i++;
a[i]=j;
dfs(i);
i--;//回溯i
a[i]=0;//回溯输出数组
}
}
}
解决方案2：
void dfs(int i){//已经放了i个数
if(i == n){//若放满i元
for(int j=1;j<=n;j++){
cout<<a[j]<<' ';
}
cout<<'\n';
return;
}
else {
//若没放满，则继续放下一元
for(int j=1;j<=k;j++){
a[i+1]=j;//直接在里面++不会影响i的值
dfs(i+1);
a[i+1]=0;//对应的只需要回溯输出数组的值
}
}
}
复杂度的分析： 原理就是再最开始的dfs(0)时，有n种可能，在 n 种可能里的每一种都有 n 种可能，这样有k^n的复杂度 每一个状态都是独立的