排列组合DFS

深度优先搜索：根据栈的特性，且每个节点只能被访问一次，
在寻找终点的过程中将当前元素入栈，若遇到死路则弹出栈顶元素，直到某个元素可以继续发散为止；
从初始节点出发，按预定的顺序扩展到下一个节点，
然后从下一节点出发继续扩展新的节点，
不断递归执行这个过程，直到某个节点不能再扩展下一个节点为止。
此时，则返回上一个节点重新寻找一个新的扩展节点。
如此搜索下去，直到找到目标节点，或者搜索完所有节点为止。

深度优先搜索算法框架

void dfs(int layers)
{
     if (到达终点)
     {
         输出结果
         return;    
     }

     for (枚举每一种可能情况)
     {
          if (当前选择满足条件)
          {
               保存结果
               dfs(layers + 1); 继续更深层递归
          }  
     }
}

图的深度优先搜索的核心思想：
(1)初始化图中所有节点未被访问
(2)从图中的某个结点s出发，访问u并标记已访问
(3)依次检查s的所有邻接点v, 如果v未被访问，则从v出发深度优先搜索。

const int MAXN = 10 + 2;
struct node {
    int to;
    int next;
} edge[MAXN*MAXN];

int head[MAXN];
bool vis[MAXN];

int cnt = 0;
void add(int u, int v)
{
    edge[cnt].to = v;
    edge[cnt].next = head[u];  // 采用头插法
    head[u] = cnt++;
}

void DFS_AL(int s)
{
    std::cout << s << " ";
    vis[s] = true;
    for (int i = head[s]; ~i; i = edge[i].next)
    {
        int v = edge[i].to;
        if (!vis[v])
            DFS_AL(v);
    }
}

int main()
{
    int arr[][2] = { { 1, 2 },{ 1, 3 },{ 1, 4 },{ 2, 4 },{ 2, 5 },{ 3, 6 },{ 4, 3 },{ 5, 4 },{ 5, 7 },{ 7, 6 } };
    int num = sizeof(arr) / sizeof(arr[0]);
    for (int i = 0; i < num; ++i)
    {
        vis[i] = false;
        head[i] = -1;
    }
    for (int i = 0; i < num; ++i)
        add(arr[i][0], arr[i][1]);

    DFS_AL(1);

    return 0;
}

n个数全排列，将问题分层，每层选择一个数

const int MAXN = 10 + 2;
bool vis[MAXN];
int path[MAXN];

void dfs_perm(int s, int n, int &sum)
{
    if (s == n+1)
    {
        ++sum;
        for (int i = 1; i <= n; ++i)
            std::cout << path[i] << " ";
        std::cout << std::endl;
        return ;
    }

    for (int i = 1; i <= n; ++i)
    {
        if (!vis[i])
        {    
            vis[i] = true;
            path[s] = i;
            dfs_perm(s+1, n, sum);
            vis[i] = false;
        }
    }
}

int main()
{
    for (int i = 0; i < MAXN; ++i)
    {
        vis[i] = false;
        path[i] = 0;
    }

    int sum = 0;
    dfs_perm(1, 3, sum);
    std::cout << sum << std::endl;

    return 0;
}

从n个数中选取m个的组合

const int MAXN = 10 + 2;
int path[MAXN];

void dfs_comb(int s, int n, int m, int &sum)
{
    if (s > m)
    {
        ++sum;
        for (int i = 1; i <= m; ++i)
            std::cout << path[i] << " ";
        std::cout << std::endl;
        return;
    }

    for (int i = 1; i <= n; ++i)
        if (path[s-1] < i)  // 组合数升序, 故互异，不需要vis[]标识元素是否已经访问
        {
            path[s] = i;
            dfs_comb(s+1, n, m, sum);
        }
}

int main()
{
    int sum = 0, n = 5, m = 3;    
    dfs_comb(1, n, m, sum);
    std::cout << sum << std::endl;

    return 0;
}