递归实现指数型枚举

第一种方法（一次枚举每个数选或者不选）

#include <iostream>
#include <algorithm>

using namespace std;

int n;
const int N = 20;
int a[N];
bool st[N];

void backtracking(int pos)
{
    if (pos > n)
    {
        for (int i = 1; i <= n; i ++ )
            if (st[i])
                cout << i << ' ';
        cout << endl;
        return ;
    }

    st[pos] = false;
    backtracking(pos + 1);

    st[pos] = true;
    backtracking(pos + 1);
}


int main()
{
    cin >> n;
    backtracking(1);
    return 0;
}

第二种方法（枚举每个位置可以放的数）

特点：需要一个end来说明需要枚举一个数，还要一个start防止全排列重复

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;
int n;
int a[N];
bool st[N];

void backtracking(int pos, int end, int start)
{
    if (pos > end)
    {
        for (int i = 1; i <= end; i ++ )
            cout << a[i] << ' ';
        cout << endl;
        return ;
    }

    for (int i = start; i <= n; i ++ )
        if (!st[i])
        {
            a[pos] = i;
            st[i] = true;
            backtracking(pos + 1, end, i + 1);
            st[i] = false;
        }
}

int main ()
{
    cin >> n;
    for (int i = 0; i <= n; i ++ )
        backtracking(1, i, 1); // 从第一个位置开始枚举，枚举到第i个位置，从第一个数开始枚举
    return 0;
}

递归实现排列型枚举

因为是全排列所以一组数据可以重复所以不需要一个start, 但是需要一个bool数组来防止相同的数字重复出现

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10;
int a[N];
bool st[N];

void backtracking(int u, int n)
{
    if (u == n)
    {
        for (int i = 0; i < n; i ++ )
            cout << a[i] << ' ';
        cout << endl;
        return ;
    }

    for (int i = 1; i <= n; i ++ )
    {
        if (!st[i])
        {
            a[u] = i;
            st[i] = true;
            backtracking(u + 1, n);
            st[i] = false;
            a[u] = 0;
        }
    }
}

int main ()
{
    int n;
    cin >> n;
    backtracking(0, n);
    return 0;
}

递归实现组合型枚举

这和递归实现排列型枚举的区别就在于排列型枚举是组合型枚举的一组数据的全排列
特点：因为不是全排列所以要一个start记录一下数的位置，这样可以避免全排列重复排列数字

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 30;
int n, m;
int a[N];
bool st[N];

void backtracking(int pos, int start, int m)
{
    if (pos > m)
    {
        for (int i = 1; i <= m; i ++ )
            cout << a[i] << ' ';
        cout << endl;
        return ;
    }

    for (int i = start; i <= n; i ++ )
    {
        st[i] = true;
        backtracking(pos + 1, i + 1, m);
    }
}

int main ()
{
    cin >> n >> m;
    backtracking(1, 1, m);// 从第1层递归开始，从第1个数开始枚举， 枚举m个数 
    return 0;
}

总结：

当需要全排列的时候要一个bool数组来记录相同数字已经使用
当需要组合数字的时候需要一个start来记录当前的开始枚举的位置
当枚举子集的时候需要end来控制枚举的个数，因为不要重复数据的排列所以还要start记录当前枚举的位置