深度优先(DFS)模板1：

void   DFS(int k)             //处理第k步
{   if  (k==n)                              //已经处理到第n步，到达目的状态 
               输出结果
    else                               //处理第k步
          for (int i=1; i<=m; i++)            //第k步中有m种可能
          {    处理第k步
                    DFS(k+1)；//进入第k+1步
          }
}

例1：多重排列问题

输出1-m个数中取n个数的所有多重排列。例如n=2，m=3的所有多重排列为：
1    1
1    2
1    3
2    1
2    2
2    3
3    1
3    2
3    3

//从1到m中取n个数，允许重复取数#include <iostream>using namespace std;int n,m, a[10];void  DFS(int k){      if  (k==n)         {       for (int i=0; i<n; i++)     cout<<a[i]<<" ";                cout<<endl;           }        else                 for (int i=1; i<=m; i++)                   {    a[k]=i;    DFS(k+1);      }}int main(){        cin>>m>>n;         DFS(0);    return 0;       }

View Code

//从1到m中取n个数，允许重复取数

#include <iostream>

using namespace std;

int n,m, a[10];

void  DFS(int k)

{      if  (k==n)        

                     {       for (int i=0; i<n; i++)  

                                                     cout<<a[i]<<" ";                 cout<<endl;           }     

    else               

                    for (int i=1; i<=m; i++)             

                              {    a[k]=i;      DFS(k+1);            }

}

int main()

{ 

       cin>>m>>n;  

       DFS(0); 

   return 0;    

   }