题解 P1164 【小A点菜】

# 这不是DFS 好吧，其实还是差不多的，但是比起下面的题解里的DFS，我没有回溯的这个过程 为什么呢，因为实际上，当我们用dfs选择某一种菜后，之后的运算会把除了前面的没有选择的菜种的所有其他方法都算一次，而当你选了前面的菜时就已经把后面的菜的某种方法已经选择了 这么说呢可能有点不清楚（好像不是一点） 打个比方吧，我们严格控制哪一个菜时第几个选择了的，例如 1 2 3 4这4种菜 当我们把1作为一号菜时 会搜索到 1 2 1 3 1 4 1 2 3 1 2 4 1 3 4 1 2 3 4 以上的所有方法 而当我们把2做开头后，上面出现过得方法就不用考虑了，实际上就是带1的都不用算了！ 便只剩 2 3 2 4 2 3 4 这3种方法了，之后把3做开头 3 4 已经只剩一个方法了！！ 所以实际上我们还可以少一次选择（由于省下的时间也不是很多就不加长代码了） ```cpp #include <iostream> using namespace std; int n,m,a[105],ans; void dfs (int pos,int mon)//pos表示每次可以从第几个开始买，mon表示已经花了多少钱了 { if (mon>=m){//如果钱花完了或者不够花了就得停下来了 if (mon==m)ans++; return; } for (int i=pos;i<=n;i++){//每次只用从可以选的地方开始 int t=mon; t+=a[i]; dfs (i+1,t); } } int main () { cin>>n>>m; for (int i=1;i<=n;i++)cin>>a[i]; dfs (1,0);//开始钱为0，所有数都可以用 cout<<ans; return 0; } ``` ###### 相似的，这里有一道我自己编的实际上思想是相同的题目 [集合子集](https://www.luogu.org/problemnew/show/T35629)