暴力的艺术：回溯算法

我的CSDN：ListerCi

一、回溯算法与DFS

回溯算法是暴力求解的一种，它能系统地搜索一个问题的所有解或者任意解。它通过深度优先搜索递归地遍历所有可能的解。遍历到解空间的某个分支时，如果确定当前分支不满足条件，那么就退回到上一步尝试别的分支。这种回退到上一步的方式就是“回溯”，判断分支是否有解就是“剪枝”。
如果你是一名新手，看完回溯的定义，你是心怀期待呢还是心乱如麻呢？其实回溯法是算法学习的入门，评价一个程序员是不是学过算法，看他会不会写回溯就可以了。因此回溯算法频繁地出现在各种笔试和面试中，当你面对一个搜索问题时，如果写出了回溯法而不是一个又一个的for循环，面试官也会觉得你的代码眉清目秀的。
回溯算法的基础是深度优先搜索（DFS），这种搜索会在一个分支上一直深入，直到遍历完该分支，之后再尝试另外的分支。DFS的伪代码如下，visited[i]数组代表i点是否访问过。

void dfs(int v) {
    visited[v] = true;
    for (v的所有邻接点w) {
        if (!visited[w])
            dfs(w);
    }
}

回溯算法就是在DFS的过程里加入了返回条件以及剪枝，下面让我们来通过Leetcode真题一步一步地去理解它。

二、Leetcode回溯真题

1. 求解子集

Leetcode地址：78. 子集
题目的意思很简单，给你一个长度为n的不包含重复数字的序列，返回该序列的所有子集。既然该序列不包含重复数字，那么子集的个数肯定是2^n（因为求子集时对每个元素都有选或者不选两个操作），算法的时间复杂度就是O(2^n)。
那么选和不选这两种操作怎么体现在程序中呢？举个例子，假设当前的序列为[1, 2, 3]，我们可以选择将元素1添加到子集中，再求剩下的序列[2, 3]的所有子集；我们也可以选择不将元素1添加到子集中，再求[2, 3]的所有子集。
这明显是一个递归的过程：对第i个元素选择之后，将结果保存，再对剩下的元素进行选择。对所有的元素选择完毕之后，得到的结果就是一个子集。

// nums为需要求子集的序列
vector<vector<int> > subsets(vector<int>& nums) {
    vector<vector<int> > result; // 保存所有的子集
    vector<int> path; // 在搜索时保存当前的子集
    search(0, nums, path, result); // 从第0个元素开始搜索
    return result;
}

// idx表示当前搜索nums[idx]
void search(int idx, vector<int>& nums, vector<int>& path, vector<vector<int> >& result) {
    // 当对所有元素选择后，就得到了一个子集
    if (idx >= nums.size()) {
        result.push_back(path);
        return; // 此处一定要返回
    }
    // 选择nums[idx] 
    path.push_back(nums[idx]);
    search(idx + 1, nums, path, result);
    // 不选择nums[idx] 
    path.pop_back();
    search(idx + 1, nums, path, result);
}

2. 全排列

Leetcode地址：46. 全排列
题目给定一个没有重复数字的序列，返回其所有可能的全排列。
上题求解子集时是对每个元素选择是否添加到子集中，而求解全排列就是选择添加哪个没有被添加过的元素到当前的排列中。因为要判断某个元素是否被选取过，所以需要一个bool visited[i]数组判断i元素是否已经被添加到排列中。

例如求解[1, 2, 3]的全排列，流程如下：
① 将1添加到第一位，此时1已经被访问，则visited[1]=true，之后的元素只能从[2, 3]中选取，最终会形成1在第一位的所有全排列[1, 2, 3]和[1, 3, 2]。
② 此时1在第一位的所有情况都遍历完成，需要将1的访问状态返还为未访问，也就是visited[1]=false。这样之后将其他数放在第一位时，依旧可以选择1跟在后面。
③ 将2添加到第一位，再跟上[1, 3]的全排列。

vector<vector<int> > permute(vector<int>& nums) {
    vector<vector<int> > result;
    vector<int> cur;
    int size = nums.size();
    // 如果nums为空，返回空结果
    if (size == 0)
        return result;
    // visited数组判断当前元素是否已经添加到全排列中
    bool* visited = new bool[size];
    for (int i = 0; i < size; ++i)
        visited[i] = false;
    dfs(0, result, cur, nums, visited);
    return result;
}

// index表示当前添加第index个数字到全排列中
void dfs(int index, vector<vector<int> >& result, vector<int> cur, vector<int>& nums, bool* visited) {
    if (index >= nums.size()) {
        result.push_back(cur);
        return;
    }
    for (int i = 0; i < nums.size(); ++i) {
        // 如果当前元素未被添加到全排列中
        if (!visited[i]) {
            // 将当前元素添加到全排列
            cur.push_back(nums[i]);
            visited[i] = true;
            dfs(index + 1, result, cur, nums, visited);
            // 返还状态
            cur.pop_back();
            visited[i] = false;
        }
    }
}

3. 组合总和

Leetcode地址：39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates中所有可以使数字和为target 的组合。candidates中的数字可以无限制重复被选取。
在这道题中，数组中的元素可以重复选取，因此不需要visited[]来判断某个数字是否被访问过。在遍历时，如果确定将candidates[i]添加到组合中，那么可以将target-candidates[i]作为下一轮递归的新target，如果新target为0，那么之前的组合就是一个解；如果小于0，那么当前分支不成立，退回到上一步；如果大于0，则可以再选取一个数字添加到组合中。

vector<vector<int> > combinationSum(vector<int>& candidates, int target) {
    vector<vector<int> > result;
    vector<int> path; // 用于保存临时的组合
    sort(candidates.begin(), candidates.end()); // 排序
    search(0, result, candidates, path, target);
    return result;
}

void search(int idx, vector<vector<int> >& result, vector<int>& candidates, 
            vector<int>& path, int target) {
    if (target == 0) {
        result.push_back(path);
        return;
    }
    if (target < 0) {
        return;
    }
    //  依此遍历可选元素
    for (int i = idx; i < candidates.size(); ++i) {
        path.push_back(candidates[i]);
        // 由于可以重复选取，因此下次递归仍旧可以从当前元素开始
        search(i, result, candidates, path, target - candidates[i]);
        // 不选择当前元素，for循环向下遍历
        path.pop_back();
    }
}

上述程序通过递归时判断target是否小于0来确认当前分支是否已经无解，这样的“剪枝”方式未免太过粗糙。如果将该程序放入OJ中运行，虽然可以通过，但是运行时间只击败了大约28%的程序，这种情况下一定存在优化的办法。
仔细查看后发现，candidates是经过由小到大排序的，如果target-candidates[i] < 0，那么target-candidates[i + 1], target-candidates[i + 2]......都是小于0的。因此search()函数可以这么优化。

void search(int idx, vector<vector<int> >& result, vector<int>& candidates, 
            vector<int>& path, int target) {
    if (target == 0) {
        result.push_back(path);
        return;
    }
    for (int i = idx; i < candidates.size(); ++i) {
        if (target - candidates[i] < 0) {
            break;
        } else {
            path.push_back(candidates[i]);
            search(i, result, candidates, path, target - candidates[i]);
            path.pop_back();
        }
    }
}

优化之后，代码的运行时间击败了98%以上的程序，当真是细节决定成败。

4. 组合总和变体

Leetcode地址：40. 组合总和 II
这道题与上一道有不少区别，一是数字可能重复，二是每个数字只能取一次。如果你认为将上一题解答中的search(i, result...)改为search(i + 1, result...)就可以的话，那你就错了。
如果只是这么修改，在candidates为[1, 1, 3]和target为4的情况下，结果中会出现两个[1, 3]，因此我们需要删掉重复结果。使用set是一个办法，但是效率低下，我们可以在外层遍历时跳过重复的数字从而达到跳过重复解的效果。

vector<vector<int> > combinationSum2(vector<int>& candidates, int target) {
    vector<vector<int> > result;
    vector<int> path;
    sort(candidates.begin(), candidates.end());
    search(0, result, path, candidates, target);
    return result;
}

void search(int idx, vector<vector<int> >& result, vector<int>& path, 
            vector<int>& candidates, int target) {
    if (target == 0) {
        result.push_back(path);
        return;
    }
    for (int i = idx; i < candidates.size(); ++i) {
        if (i > idx && candidates[i] == candidates[i - 1])
            continue;
        if (target - candidates[i] < 0) {
            break;
        } else {
            path.push_back(candidates[i]);
            search(i + 1, result, path, candidates, target - candidates[i]);
            path.pop_back();
        }
    }
}

如果你一时无法理解，可以在纸上模拟一下代码的流程。

三、八皇后

讲到回溯就绕不开八皇后问题，因为它实在是太经典了，Leetcode上有一道变种的N皇后问题，让我们来一探究竟。
Leetcode地址：51. N皇后
国际象棋中，皇后可以攻击同一直线和同一斜线的棋子。如果想要在N*N的棋盘上放置N个皇后，使它们之间互不攻击，就意味着每行、每列、每条斜线上都只有一个皇后。下图就是八皇后的一个解。

8-queens.png

一个N*N的棋盘，显然只有N行N列，那么每一行每一列上都会有一个皇后。那么这个棋盘有多少条斜线呢？初中数学告诉我们，正斜线和反斜线都有2N-1条。其中正斜线的斜率都为1，反斜线的斜率都为-1。
正斜线的公式为y = x + k1，反斜线的公式为y = -x + k2。其中，k1和k2的取值都有2N-1种，每个k1都能确定一条正斜线，每个k2都能确定一条反斜线。所以使用两个数组就能确定每条斜线是否已经被一个皇后占据了。（上述的斜率是在标准坐标系中的，二维数组的坐标系并不是如此。）
假设当前需要在(i, j)放置一个皇后，那么i所代表的行和j所代表的列必须没有被占据，而i - j和i + j所代表的两条斜线也必须没有被占据。为了节省空间，我们使用一维数组path[]来存储皇后的摆放情况，path[i] = val代表i行val列有一个皇后。因为每行都必须有一个皇后，可以直接遍历行来存放。

vector<vector<string> > solveNQueens(int n) {
    vector<vector<string> > result;
    // path[i] = val 代表i行val列有一个皇后
    int* path = new int[n];
    // 标记某一列是否被占据
    bool* visited = new bool[n];
    for (int i = 0; i < n; ++i)
        visited[i] = false;
    // 标记两条斜线是否被占据
    bool* slash1 = new bool[2 * n];
    bool* slash2 = new bool[2 * n];
    for (int i = 0; i < 2 * n; ++i) {
        slash1[i] = false;
        slash2[i] = false;
    }
    search(0, result, path, n, visited, slash1, slash2);
    return result;
}

void search(int idx, vector<vector<string> >& result, int* path, int n, 
            bool* visited, bool* slash1, bool* slash2) {
    // 这里是生成返回结果的，不重要
    if (idx >= n) {
        vector<string> tmp_result;
        for (int i = 0; i < n; ++i) {
            // 每一行
            char* tmp = new char[n + 1];
            for (int j = 0; j < n; ++j) {
                if (path[i] == j)
                    tmp[j] = 'Q';
                else
                    tmp[j] = '.';
            }
            tmp[n] = '\0';
            string tmp_string(tmp);
            tmp_result.push_back(tmp_string);
        }
        result.push_back(tmp_result);
        return;
    }
    // 在每一行添加一个皇后
    for (int i = 0; i < n; ++i) {
        if (!visited[i] && !slash1[idx + i] && !slash2[idx - i + n]) {
            // 该位置合法，尝试在这里摆放一个皇后
            path[idx] = i;
            visited[i] = true;
            slash1[idx + i] = true;
            slash2[idx - i + n] = true;
            search(idx + 1, result, path, n, visited, slash1, slash2);
            // 不在此处摆放，返还状态
            visited[i] = false;
            slash1[idx + i] = false;
            slash2[idx - i + n] = false;
        }
    }
}