回溯算法

可解决的问题

• 组合问题：N个数里面按一定规则找出k个数的集合
• 切割问题：一个字符串按一定规则有几种切割方式
• 排列问题：N个数按一定规则全排列，有几种排列方式
• 棋盘问题：N皇后，数独等等

总结模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

• 回溯法抽象为树形结构后，其遍历过程就是：for循环横向遍历，递归纵向遍历，回溯不断调整结果集。
• 一般需要两个全局变量，或者放在函数形参里面；

vector<vector<int>> result; // 存放符合条件结果的集合
vector<int> path; // 用来存放符合条件结果

• 还有一个可选的位于回溯函数形参的int型startIndex变量，用来记录本层递归中，集合从哪里开始遍历；

• 组合问题，startIndex用在循环中for (int i = startIndex; i < n; i++);

• 排列问题，不用startIndex，是`for (int i = 0; i < n; i++);

• 不重复选取某一元素backTrack(candidates, target, i);

• 重复选取某一元素backTrack(candidates, target, i + 1);

• 结果集去重，注意先排序；

• • 组合问题可以使用下标去重：if (i > startIdx && nums[i] == nums[i - 1]) continue;
  • 排列问题去重使用bool数组，注意树枝和树层去重，最好画N叉树图看，更直观；
  • 也还可以使用set集合去重；

• 字符串分割时要有判断条件if (isValid(s, startIndex, i));

组合问题

一个集合

• 需要startIndex；
• 递归传参时i+1表示不能重复使用元素；
• 递归传参时i表示可以重复使用元素；

集合元素唯一

①如果是一个元素唯一的集合来求组合的话，就需要startIndex，并且递归时用i+1；

for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
    path.push_back(i); // 处理节点 
    backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
    path.pop_back(); // 回溯，撤销处理的节点
}

②如果题目说明可以重复选取元素，则仍然用startIndex，但递归时不用i+1而是i；

for (int i = startIndex; i < candidates.size(); i++) {
    sum += candidates[i];
    path.push_back(candidates[i]);
    // 关键点:不用i+1了，表示可以重复读取当前的数
    backtracking(candidates, target, sum, i); 
    sum -= candidates[i];   // 回溯
    path.pop_back();        // 回溯
}

集合元素不唯一

即组合去重问题，集合（数组）有重复元素，但还不能有重复的组合，一般要求集合即数组排序。仍然需要用到startIndex，并且加一个bool型数组used，用来记录同一树枝上的元素是否使用过。要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

在candidates[i] == candidates[i - 1]的情况下：

• used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
• used[i - 1] == false，说明同一树层candidates[i - 1]使用过

for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
    // 要对同一树层使用过的元素进行跳过
    if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
        continue;
    }
    // 要对同一树层使用过的元素进行跳过，使用startIndex去重，就可以不用used数组
    //if (i > startIndex && candidates[i] == candidates[i - 1]) {
    //    continue;
    //}
    sum += candidates[i];
    path.push_back(candidates[i]);
    used[i] = true;
    backtracking(candidates, target, sum, i + 1, used); 
    used[i] = false;
    sum -= candidates[i];
    path.pop_back();
}

多个集合

如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合，本题增加index来表示深度，以判断递归结束条件。

for (int i = 0; i < letters.size(); i++) {
    s.push_back(letters[i]);            // 处理
    backtracking(digits, index + 1);    // 递归，注意index+1，下层要处理下一个数字了
    s.pop_back();                       // 回溯
}

排列问题

无重复元素的序列

例：给定一个没有重复数字的序列，返回其所有可能的全排列。

输入: [1,2,3]

输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

思路：

• 不用startIndex
• 需要一个used数组，标记已经选择的元素

当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

for (int i = 0; i < nums.size(); i++) {
    if (used[i] == true) continue; // path里已经收录的元素，直接跳过
    used[i] = true;
    path.push_back(nums[i]);
    backtracking(nums, used);
    path.pop_back();
    used[i] = false;
}

注意：

• 每层都是从0开始搜索
• 需要used数组记录path里都放了哪些元素了

有重复元素的序列

例：输入：nums = [1,1,2]

输出： [[1,1,2], [1,2,1], [2,1,1]]

需要去重，去重一定要对元素进行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。

void backtracking (vector<int>& nums, vector<bool>& used) {
    // 此时说明找到了一组
    if (path.size() == nums.size()) {
        result.push_back(path);
        return;
    }
    for (int i = 0; i < nums.size(); i++) {
        // used[i - 1] == true，说明同一树枝nums[i - 1]使用过
        // used[i - 1] == false，说明同一树层nums[i - 1]使用过
        // 如果同一树层nums[i - 1]使用过则直接跳过
        if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
            continue;
        }
        if (used[i] == true) continue;// path里已经收录的元素，直接跳过
        used[i] = true;
        path.push_back(nums[i]);
        backtracking(nums, used);
        path.pop_back();
        used[i] = false;
    }
}

对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高！

分割问题

切割问题类似组合问题，需要startIndex；

对于分割回文串问题：

vector<vector<string>> result;
vector<string> path; // 放已经回文的子串
void backtracking (const string& s, int startIndex) 

注意切割过的位置，不能重复切割，所以是backtracking(s, i + 1); 传入下一层的起始位置为i + 1。

for (int i = startIndex; i < s.size(); i++) {
    if (isValid(s, startIndex, i)) {   // 是回文子串
        // 获取[startIndex,i]在s中的子串
        string str = s.substr(startIndex, i - startIndex + 1);
        path.push_back(str);
        backtracking(s, i + 1); // 寻找i+1为起始位置的子串
        path.pop_back(); 		// 回溯过程，弹出本次已经填在的子串
    } else {             		
        continue;// 不是回文，跳过；有时是break，不合法，直接结束本层循环例如ip地址。
    }
}

棋盘问题

• 写回溯算法的时候，一般函数返回值都是void；

• 但也有bool的时候，就是需要在树形结构中找到唯一的一条通向叶子节点的路线

例一，N皇后

因为是每一行都放一个皇后，所以是一维递归；

// n 为输入的棋盘大小
// row 是当前递归到棋盘的第几行了
void backtracking(int n, int row, vector<string>& chessboard) {
    if (row == n) {
        result.push_back(chessboard);
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
            chessboard[row][col] = 'Q'; // 放置皇后
            backtracking(n, row + 1, chessboard);
            chessboard[row][col] = '.'; // 回溯，撤销皇后
        }
    }
}

例二，数独

二维递归！

bool backtracking(vector<vector<char>>& board) {
    for (int i = 0; i < board.size(); i++) {        // 遍历行
        for (int j = 0; j < board[0].size(); j++) { // 遍历列
            if (board[i][j] != '.') continue;
            for (char k = '1'; k <= '9'; k++) {     // (i, j) 这个位置放k是否合适
                if (isValid(i, j, k, board)) {
                    board[i][j] = k;                // 放置k
                    if (backtracking(board)) return true; // 如果找到合适一组立刻返回
                    board[i][j] = '.';              // 回溯，撤销k
                }
            }
            return false;                // 9个数都试完了，都不行，那么就返回false
        }
    }
    return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
}

---

【参考资料】代码随想录、力扣