生成序列的算法

下面简单介绍了生成排列组合的算法。这常常用于穷举所有的可能。

排列的算法时间复杂度总为 \(n!\)，没有什么优化方法。

下面是全排列的算法：

暴力法

对于一个规模为 \(n\) 的全排列问题，我们知道，若 \((n-1)!\) 已经完成了排列，则我们只需要将 \(n\) 插入到 \((n-1)!\) 所有序列的所有位置即可。

比如对于排列 \([1, 2, 3]\)，我们知道 \(2!\) 的所有可能为：

[1, 2]
[2, 1]

将 3 插入上面序列的所有位置，得到：

[3, 1, 2]
[1, 3, 2]
[1, 2, 3]

[3, 2, 1]
[2, 3, 1]
[2, 1, 3]

根据这种思想，我们可以写出下面的算法：

vector<vector<int>> permute(vector<int> &nums) {
    if(nums.empty()) {
        return {};
    }
    if(nums.size() == 1) {
        return { nums };
    }

    auto val = nums[nums.size() - 1];
    nums.pop_back();

    auto res = vector<vector<int>>();

    auto sub_permute = permute(nums);
    for(auto const &sub : sub_permute) {
        for(int i = 0; i <= sub.size(); ++i) {
            auto cpy = sub;
            cpy.insert(cpy.begin() + i, val);
            res.push_back(cpy);
        }
    }

    return res;
}

基于多叉树的生成

可以将全排列问题看作一个多叉树遍历的问题，假设有一个排列 \([1, 2, 3]\)，则有下面的树：

对于这样的多叉树而言，每条路径完整的遍历都是一个排列。

实现上，我们定义一个 pre 序列和一个 remains 序列。每次循环中我们都从 remains 中取出一个数字，然后将这个数字追加到 pre 序列后面。这样就生成了一层的遍历结果。然后将 pre 和剩余的 remains 传递个下一层。如此反复，一旦 remains 为空，就意味着已经遍历结束，可以将结果返回了：

vector<vector<int>> permute(vector<int>& nums) {
    auto res = vector<vector<int>>();

    visit(res, {}, nums);
    return res;
}

void visit(vector<vector<int>>& res, vector<int> p, vector<int> remains) {
    if(remains.empty()) {
        res.push_back(p);
        return;
    }

    for(int i = 0; i < remains.size(); ++i) {
        auto cpy = remains;
        cpy.erase(cpy.begin() + i);
        auto cpy2 = p;
        cpy2.push_back(remains[i]);
        visit(res, cpy2, cpy);
    }
}