回溯递归算法

2021-06-24 本文已影响0人上官宏竹

回溯大法严重依赖【递归】

1、求子集

回溯准备一

1、一个可以移动的指针，比如代表数组下标的i。
2、一个存储临时数据的item
3、一个存储结果数据的result

回溯准备二

分析：这里任何一个数据都存在两种状态，“放”或者“不放”入集合。放入集合，递归进行后续的步骤；之后将其拿出来，即选择不放入，递归进行后续的步骤。

定义回溯函数参数

一个数组下标指针、一个原始数组、一个item、一个result

解答代码

void gen(int i, vector<int>& nums, vector<int>& item, vector<vector<int>>& result)
{
    if (i >= nums.size()) {
        return;
    }
    item.push_back(nums[i]);
    result.push_back(item);
    gen(i + 1, nums, item, result);

    item.pop_back();
    gen(i + 1, nums, item, result);
}

2、括号生成

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

思路

先使用求子集的方法，即回溯法把所有括号生成出来，在放置入结果时判断该组是否为有效括号，即可。

定义回溯函数参数

一个数组下标指针：此时并没有传入数组，因为括号就两个“(”、“)”，所以直接传入。
一个原始数组：同上
一个item、一个result

解答代码

void gen(int n, const string& item, vector<string>& result)
{
    if (item.size() == 2 * n) {
        if (iscorrect(item)) {  // 是正确的括号对
            result.push_back(item);
        }
    }

    gen(n, item + '(', result);
    gen(n, item + ')', result);
}

3、八皇后

解决点1、任意点放置一个皇后，更新棋盘mark[][]数组

设置一个方向数组，根据数组一次性更新好mark，并实现之。

方向数组
实现PutDownTheQueen(int x, int y, vector<vector>& mark)

解决点2、回溯按行扫描

因为每一行只能放一个皇后，那么按行进行扫描，找到一行时，在mark数组中按列寻找可以放置的位置，找到则放置一个皇后，然后更新mark数组，进行下一轮的递归；该行找不到一个位置放置时，需要进行回溯。而此时，需要回退mark数组到上一个状态，如此则需要记录使用前的mark数组。

解答代码


void gen(
    int k,  // k代表当前处理第k列，及放置了k个皇后
    int n,  // n个皇后
    vector<string>& item,           // 某次的结果        
    vector<vector<string>>& result, // 最终结果
    vector<vector<int>>& mark)      // 标记数组，用于判断当前位置是否可以放置皇后，初始化为0，放置皇后置为1      
{
    if (k == n) {
        // 放置了n个皇后，说明完成了一次皇后的放置，则存储好结果
        result.push_back(item);
        return;
    }

    // 每次按列去扫描，寻找可放置皇后的位置
    for (int i = 0; i < n; i++) {
        if (mark[k][i] == 0) {  // 第k行，i列可放置皇后
            vector<vector<int>> tmpmark = mark; // 关键点，进行递归处理前把mark数组保存起来

            item[k][i] = 'Q';                   // 记录皇后的位置
            PutDownTheQueen(k, i, mark);        // 此处放置一个皇后，更新mark数组
            gen(k + 1, n, item, result, mark);  // 递归处理下一行

            // 下一行处理完毕后，恢复现场，回到回溯前的状态
            mark = tmpmark;
            item[k][i] = '.';
        }
    }
}

解释：如下图，当k=3时，for (int i = 0; i < n; i++)这个for循环没有一列满足情况，其实这一次寻找就失败了，即Q在(0,0),(1,2)处就不满足要求，需要回退到k=2去寻找下一个位置，即需要找第2行第2列以后的列了，此时你并不需要考虑第2行第2列那个位置是否需要在mark数组里置为不可访问的点了，因为根据这个for循环，它也不会再去找这个点了，只会往后找。而在开始对第2行第3列的处理前，需要恢复下mark数组。

k从1遍历到2
mark数组的变化如下图：

mark数组

01迷宫

求所有从左上角走到右下角的路径，1可走，0不可走。方向选择为：上、下、左、右。

01迷宫

namespace {
    int dx[] = {0, -1, 0, 1};
    int dy[] = {-1, 0, 1, 0};
}

class Solution2 {
    bool canVist(vector<vector<int>>& k, int x, int y)
    {
        if (x < 0 || y < 0 || x >= k.size() || y >= k[0].size()) {
            return false;
        }
        return true;
    }

public:
    void dfs(vector<vector<int>>& k, int x, int y, vector<vector<int>>& vist, 
        vector<pair<int, int>>& item, vector<vector<pair<int, int>>>& result)
    {
        if (!canVist(k, x, y)) {
            return;
        }

        if (x == k.size() - 1 && y == k[0].size() - 1) {
            // 找到一个解
            item.push_back(make_pair(x, y));
            result.push_back(item);
            return;
        }

        for (int i = 0; i < 4; i++) {
            int next_x = x + dx[i];
            int next_y = y + dy[i];

            if (!canVist(k, next_x, next_y)) {
                // 防止越界操作
                continue;
            }

            // 可达、未访问
            if (k[next_x][next_y] == 1 && vist[next_x][next_y] == 0) {
                // 记录
                vist[x][y] = 1;                  // 当前点标记为已访问
                item.push_back(make_pair(x, y)); // 记录当前点

                dfs(k, next_x, next_y, vist, item, result);

                // 恢复
                vist[x][y] = 0;
                item.pop_back();
            }
        }
    }

    void search(vector<vector<int>> k)
    {
        vector<vector<int>> vist(k.size(), vector<int>(k[0].size(), 0));
        bool find = false;
        vector<pair<int, int>> item;
        vector<vector<pair<int, int>>> result;

        dfs(k, 0, 0, vist, item, result);

        for (auto e : result) {
            for (auto f : e) {
                cout << "(" << f.first << "," << f.second << ")" << endl;
            }
            cout << endl;
        }
    }
};

vector<vector<int>> a{
    {1, 1, 1, 0, 1, 1, 1, 1},
    {1, 0, 0, 0, 0, 1, 0, 1},
    {1, 1, 1, 1, 1, 1, 0, 1},
    {0, 1, 0, 0, 0, 0, 0, 1},
    {0, 1, 0, 1, 1, 1, 1, 1},
    {1, 1, 0, 1, 0, 0, 0, 0},
    {1, 0, 0, 1, 0, 1, 1, 1},
    {1, 1, 0, 1, 1, 1, 0, 1}
};
vector<vector<int>> b{
    {1, 1, 1, 0},
    {0, 1, 1, 0},
    {0, 1, 0, 0},
    {0, 1, 1, 1}
};

参考其他题目如下：
地下迷宫