一? ?火星人?

?拿到這種類似于排序的，這個就好比如我們之前學習dfs基礎的時候里面的指數型枚舉

指數型枚舉	數據與數據之間沒有任何枚舉，就比如選這個數字與不選
組合型枚舉	數據與數據之間有聯系，下一個數字不可以給上一個數字
排列型枚舉	數據與數據之間有聯系，下一個數字比上一個數字加1

?所以我們刨析這個題目也就是這樣我們以它的例子來講解
也就是這樣的一個排序方式
那我們這種，首先是每個數據與每個數據是有關系的，其次就是這個這個每次的對應的值都不可以給上一個，那么這種就是組合型枚舉

我們就用之前所學過的組合型枚舉來敲一遍代碼

#include<stdio.h>
#include<algorithm>
#include<cstring>
using namespace std;const int N=10010;
int m;           //手指數
int n;           //加的位數
int res=0;         //記錄加的次數
int ans[N];      //答案寄存數組
int mas[N];      //火星人所給的數字
int st[N]={0};   //表示狀態數
bool return0 = false;void dfs(int x){if(return0 == true){return ;}if(x>m){res++;if(res==n+1){for(int i=1;i<=m;i++){printf("%d ",ans[i]);}return0 = true;}return;}for(int i=1;i<=m;i++){if(res==0){i=mas[x];}if(st[i]==0){ans[x]=i;st [i]=1;dfs(x+1);ans[x]=0;//清理現場st [i]=0;}}
}int main(){scanf("%d",&m);scanf("%d",&n);for(int i=1;i<=m;i++){scanf("%d",&mas[i]);}dfs(1);return 0;
}

?我們這里寫了一個減枝的操作前面的return0這個是用來減枝的，因為最后會有數據過不去

二? 烤雞

?我們來分析這個題目，這個題目是有很多的烤雞的調料，然后有10種調料，這每個調料都是有對應的3個不同重量的，然后我們輸入一個重量，然后剩下的調料的重量要等于這個重量
我們這里就是指數型枚舉，3個重量都有選擇或者不選擇，但是這里一定要有10種調料的種類
?

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N = 20;int n;
int ret;
int ans[N];
int mem[59055][N];void dfs(int x,int sum){if(sum>n) return;    //減枝if(x>10){if(sum==n){ret++;for(int i=1;i<=10;i++){mem[ret][i]=ans[i];}}return ;}for(int i=1;i<=3;i++){ans[x]=i;dfs(x+1,sum+i);ans[x]=0;}}int main(){scanf("%d",&n);dfs(1,0);printf("%d\n",ret);for(int i=1;i<=ret;i++){for(int j=1;j<=10;j++){printf("%d ",mem[i][j]);}printf("\n");}return 0;
}

?在計算指數型枚舉的時候，我們的打印里面一定要有一個限制值，根據題目的不同來定，如果沒有限制的話會進行重復的打印，有的題目是要求前面打印過之后后面不可以進行打印，有些是可以運行重復但是又限制條件

---

總結：

遞歸指數型枚舉就是我們看題目的時候有選擇或不選擇的時候，一般都是指數型枚舉，然后我們就要審題，題目如果有給限制條件的話，那么就是要利用限制條件來進行解決，如果沒有的話就是要用到它當前的狀態來決定，也就是狀態數組

遞歸指數型枚舉就是我們看到題目的時候，題目給我們有那種規律的，也就是類似于排序的，而且類似字典序的，一般就是要用到指數型枚舉，但是這個一般都是前面用了那個數字，后面不許用，所以這個一般是要用到記憶數組的