1.找整个递归的终止条件 : 递归应该在什么时候结束?
2.找返回值 : 应该给上一级返回什么信息?
3.本级递归应该做什么 : 在这一级递归中,应该完成什么任务?

排列包含次序,组合不包含次序
1.递归求全排列(考虑次序)
2.递归求所有组合(不考虑次序)
3.递归求其中m个数的全排列(不考虑次序)

1.递归求全排列(考虑次序)
#include<iostream>
using namespace std;
const int N=10;
int pa[N];   //当前位置选那个数字
int st[N];   //这个数字选过了没
int n;
void dfs(int u)
{
    if(u>n)
    {
        for(int i=1;i<=n;i++) cout<<path[i]<<" ";
        cout<<endl;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!state[i])
        {
            path[u]=i;
            state[i]=1;
            dfs(u+1);
            state[i]=0;
        }
    }
}
int main()
{
    cin>>n;
    dfs(1);  //目前选到那个位置了
    return 0;
}

2.递归求所有组合(不考虑次序)
#include<iostream>
#include<string>
using namespace std;
const int N=16;
int n;
int st[N];   //当前位置选不选数字
void dfs (int u)
{
    if(u>n)
    {
        for (int i=1;i<=n;i++)
            if (st[i]==1) cout<<i<<" ";
        cout<<endl;
        return;
    }
    st[u]=2;
    dfs (u+1);
    st[u]=1;
    dfs (u+1);
}
int main()
{
    cin>>n;
    dfs (1);   //目前选到那个位置了
    return 0;
}

3.递归求其中m个数的全排列(不考虑次序)
#include<iostream>
#include<algorithm>
using namespace std;
const int N=20;
int n,m;
int pa[N];   //一共有多少个位置
void dfs (int u,int s)
{
    if (u>m)
    {
        for (int i=1;i<=m;i++) cout<<pa[i]<<" ";
        cout<<endl;
        return;
    }
    for (int i=s;i<=n;i++)
    {
        pa[u]=i;
        dfs (u+1,i+1);
    }
}
int main()
{
    cin>>n>>m;
    dfs(1,1);   //目前选到那个位置了,从那个数字开始选
    return 0;
}