汉诺塔¶

汉诺塔常见的形式有输出移动的次数；或者如一本通1205，输出具体的盘子编号和移动方式；或者增加一个杆。

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstdio>

using namespace std;

int step = 0;

//借助tmp从start移到finish
void Hanoi(int n, char start, char finish, char tmp)
{
    if (n == 1) {
        ++step;
        // cout << start << "->" << n << "->" << finish << endl;
        printf("%c->%d->%c\n", start, n, finish);
        return;
    }

    //借助finish将上面的n-1个从start移到tmp
    Hanoi(n - 1, start, tmp, finish);
    ++step;
    //cout << start << "->" << n << "->" << finish << endl;
    printf("%c->%d->%c\n", start, n, finish);
    //借助start将tmp的n-1个移到finish
    Hanoi(n - 1, tmp, finish, start);
}

int main()
{
    // std::ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);

    int n;
    cin >> n;
    char left, middle, right;
    cin >> left >> middle >> right;
    Hanoi(n, left, middle, right);

    return 0;
}

递归实现指数型枚举¶

来源于《算法竞赛进阶指南》递推与递归章节。输出1~n的所有可能的组合，包括空。

#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>

using namespace std;

int n;
vector<int> res;

ostream & operator<<(ostream & os, const vector<int> & v)
{
    for (auto e : v) os << e << " ";
    os << endl;

    return os;
}

void calculate(int x)
{
    if (x == n + 1) {
        cout << res;
        return;
    }

    //不选择
    calculate(x + 1);
    res.push_back(x); //选择x
    calculate(x + 1);
    res.pop_back(); //恢复原状
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    calculate(1);

    return 0;
}

递归实现组合型枚举¶

从1~n这n（ $n\leq 20$ ）个数中随机选出m个，输出所有可能的组合。

#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

int n, m;
vector<int> res;

ostream & operator<<(ostream & os, const vector<int> & v)
{
    for (auto e : v) os << e << " ";
    os << endl;

    return os;
}

void calculate(int x)
{
    if (res.size() > m || res.size() + n - x + 1 < m)
        return;

    if (x == n + 1) {
        cout << res;
        return;
    }

    res.push_back(x); //选择x
    calculate(x + 1);
    res.pop_back(); //恢复原状
    //不选择
    calculate(x + 1);
}


int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m;
    calculate(1);

    return 0;
}

相比较递归实现指数型枚举，这里多了剪枝，即如果当前选择的数量超过了m，或者剩下的所有数据都选也无法达到m，那么就应该及时返回，避免无用的搜索。

递归实现排列型枚举¶

将1~n这n $(n < 10)$ 个数排成一行后打乱顺序，输出所有可能的次序。按由小到大的顺序输出。

#include <iostream>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <climits>
#include <cstdio>
#include <cstdlib>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

vector<bool> used(15, false);
int n;

ostream & operator<<(ostream & os, const vector<int> & v)
{
    for (int i = 0; i < n; ++i) os << v[i] << " ";
    os << endl;
    return os;
}

void DFS(int x, vector<int> & res)
{
    if (x == n + 1) {
        cout << res;
        return;
    }

    for (int i = 1; i <= n; ++i) {
        if (used[i]) continue;
        res[x - 1] = i;
        used[i] = true;
        DFS(x + 1, res);
        used[i] = false; //恢复原状
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n; 
    vector<int> res(n);
    DFS(1, res);

    return 0;
}

第二种回溯框架

#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <set>
#include <algorithm>

using namespace std;

vector<bool> used(10, false);
vector<int> res(10);

void DFS(int k, int n)
{
    for (int i = 1; i <= n; ++i) {
        if (!used[i]) {
            res[k] = i;
            used[i] = true;

            if (k == n) {
                for (int index = 1; index <= n; ++index) {
                    cout << res[index] << " ";
                }
                cout << endl;
            }
            else DFS(k + 1, n);

            used[i] = false;
        }
    }
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n;
    cin >> n;

    res[0] = 1;
    DFS(1, n);

    return 0;
}

典型问题：