STAy's Blog

落叶的一生，只为了归根么？

【算法】回溯

发布于 2021-11-02 | 19分钟 | 3855字数

回溯其实就是DFS的一种，通常DFS需要有一个全局的纪录，记录哪些节点被访问过了。

回溯是递归的副产品，只要有递归就会又回溯，另外回溯法不是什么高效的算法，因为回溯本质上是穷举，如果想要高效一些，需要加上剪枝。

回溯一般能解决的问题：

  1. 组合问题：N个数中按一定规则找出k个数的集合；
  2. 切割问题：一个字符串按一定规则有几种切割方式；
  3. 子集问题：N个数的集合里有多少符合条件的子集；
  4. 排列问题：N个数按一定规则全排列，有几种排列方式；
  5. 棋盘问题：N皇后，解数独等

回溯问题都可以抽象为树形结构，在集合中递归查找某些元素，集合的大小就构成了树的宽度，递归的深度就是树的深度。for循环是树的横向遍历，递归是树的深度遍历。

模板：

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

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

组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

class Solution {
public:
    vector<vector<int> > res;
    vector<int> tmpres;
    vector<vector<int>> combine(int n, int k) {
        backtracing(1, n, k);
        return res;
    }

    void backtracking(int index, int n, int k) {
        if (tmpres.size() == k) {
            res.push_back(tmpres);
            return ;
        }
        // for (int i = index; i <= n - (k - tmpres.size()) + 1; i ++) { // 剪枝
        for (int i = index; i <= n; i ++) {
            tmpres.push_back(i);
            backtracing(i + 1, n, k);
            tmpres.pop_back();
        }
        return ;
    }
};

这里可以做一个剪枝优化，就是如果剩下的待选择的数的个数小于需要的个数的话，那么就没有必要遍历了，例如n=4，k=4，那么index从2开始的后面的数就没必要遍历了，因为肯定不够四个数了。

  • 已经选择元素的个数：tmpres.size()
  • 还需要选择的个数：k - tmpres.size()
  • 在集合中至多要起始的位置：n - (k - tmpres.size()) + 1
  • 例如，n=4， k=3， 那么当一个元素没有选tmpres.size() == 0时，至少要从2开始遍历，如果从3开始遍历显然后面的数字就不够k个了。

组合总和1

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

class Solution {
public:
    vector<vector<int> > res;
    vector<int> tmp;
    int visit[10] = {0};
    vector<vector<int>> combinationSum3(int k, int n) {
        backtracking(1, k, n, 0);
        return res;
    }

    void backtracking(int index, int k, int n, int sum) {
        // if(sum > n) return ; // 剪枝
        if (tmp.size() == k && sum == n) {
            res.push_back(tmp);
            return ;
        }
        // for (int i = index; i <= 9 - (k - tmp.size()) + 1; i ++) { // 剪枝
        for (int i = index; i <= 9; i ++) {
            if (visit[i] != 1) {
                tmp.push_back(i);
                visit[i] = 1;
                backtracking(i + 1, k, n, sum + i);
                visit[i] = 0;
                tmp.pop_back();
            }
        }
    }
};

剪枝就是如果当前tmp中所有数的和已经大于n了，那么后面的遍历也就没意义了，肯定更大了，所以if(sum > n) return ;，另外如果剩下的数的个数不够了，显然也不用继续遍历了，即：i <= 9 - (k - tmp.size() + 1)。

电话号码的字母组合

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/submissions/

手机9宫格按键，例如输入"23"，可能出现的字符组合为["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。

class Solution {
public:
    vector<string> res;
    vector<char> tmp;
    string number_str[11] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> letterCombinations(string digits) {
        if(digits == "") return res;
        int k = digits.length();
        backtracking(digits, 0, k);
        return res;
    }

    void backtracking(string digits, int digits_index, int k) {
        if (digits_index == k) {
            string str = "";
            for (int i = 0; i < k; i ++) {
                str += tmp[i];
            }
            res.push_back(str);
            return ;
        }
        string str = number_str[digits[digits_index] - '0'];
        for (int i = 0; i < str.length(); i ++) {
            tmp.push_back(str[i]);
            backtracking(digits, digits_index + 1, k);
            tmp.pop_back();
        }

        return ;
    }
};

思路大概就是按照输入的数字，对于每个数字挑出一个字符，树的深度就是键入的数字的个数，宽度就是最长是4。终止条件就是选取的字符的个数等于键入的数字的个数时。

组合总和2

https://leetcode-cn.com/problems/combination-sum/

给定一个无重复元素的正整数数组 candidates 和一个正整数 target ，找出 candidates 中所有可以使数字和为目标数 target 的唯一组合，candidate中的元素可以多次使用，但结果中不能存在相同的子集。

class Solution {
public:
    vector<vector<int> >res;
    vector<int> tmp;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        if(candidates.size() == 0 || target == 0) return res; 
        backtracking(candidates, target, 0, 0);
        return res;
    }

    void backtracking(vector<int>& candidates, int target, int sum, int index) {
        if(sum > target) return ;
        if (sum == target) {
            res.push_back(tmp);
            return ;
        }
        for (int i = index; i < candidates.size(); i ++) {
            tmp.push_back(candidates[i]);
            backtracking(candidates, target, sum + candidates[i], i);
            tmp.pop_back();
        }
    }
};

这里需要注意的是index 不是从i+1开始了，而是从i开始，因为可以有重复元素。

组数总和3

https://leetcode-cn.com/problems/combination-sum-ii/

这道题在之前的基础上，candidate数组中的元素有重复的了，但是每个元素只能使用一次。

有重复的就需要去重，在树形结构中重复分为两个维度，第一个维度就是一个树枝上的重复元素，另一个维度就是从一层上的重复元素，这道题显然是需要去除同一层上的重复元素。

同一层上的元素，就是同一个for循环中，也就是如果该for循环用过了某个元素，那么应该标记一下它，下次再到它时就跳过。但是需要先排序。原因是：例如1，7，1，target=8，如果不排序，就算在一个for循环中标注了1使用过，还是会有重复的[1,7]和[7,1]，原因是虽然1标注使用过，但是如果7开头时，递归下去之后，下一层的for循环对1还是没有标注使用过。

class Solution {
public:
    vector<vector<int> > res;
    vector<int> tmpres;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtracking(candidates, target, 0, 0);
        return res;
    }

    void backtracking(vector<int>& candidates, int target, int sum, int index) {
        if(sum > target) return ;
        if (sum == target) {
            res.push_back(tmpres);
            return ;
        }
        int used[101] = {0};
        for (int i = index; i < candidates.size(); i ++) {
            if (used[candidates[i]]) continue;
            used[candidates[i]] = 1;
            tmpres.push_back(candidates[i]);
            backtracking(candidates, target, sum + candidates[i], i + 1);
            tmpres.pop_back();
        }
        return ;
    }
};

分割回文串※

https://leetcode-cn.com/problems/palindrome-partitioning/

切割字符串其实和组合问题相似，对于字符串abcdef：

  • 组合问题：选取一个a之后，在bcdef中再选取第二个，选取b之后在cdef中选第三个...
  • 切割问题：切割一个a之后，在bcdef中再切割第二段，然后切割第三段...

唯一不同点在于，在切割前需要判断一下待切割的字符串是不是回文。

对于每一层递归，startIndex代表起始字符，然后看s[startIndex, i]是不是回文，如果是，那么就将其截取，进入下一层递归，起始字符是i+1，如果s[startIndex, i]不是回文，那就接着判断s[startIndex, i+1]是不是回文...

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> tmpans;
    vector<vector<string>> partition(string s) {
        backtrancing(s, 0);
        return ans;
    }

    void backtracking(string s, int startIndex) {
        if (startIndex == s.length()) {
            ans.push_back(tmpans);
            return ;
        }
        for (int i = startIndex; i < s.length(); i ++) {
            if (isH(s, startIndex, i)) {
                tmpans.push_back(s.substr(startIndex, i - startIndex + 1));
                backtrancing(s, i + 1);
            }
            else continue;
            tmpans.pop_back();
        }
    }


    bool isH(string str, int start, int end) {
        int len = str.length();
        for (int i = start, j = end; i <= j; i ++, j --) {
            if(str[i] != str[j]) return false;
        }
        return true;
    }
};

复原IP地址

https://leetcode-cn.com/problems/restore-ip-addresses/

这道题其实也是字符串分割问题，只不过相比回文分割来说，限制的条件发生了变化，这次是看分割的字串是不是合法的ip地址范围，只需要在每次分割之前判断是否符合条件即可。

class Solution {
public:
    vector<string> res;
    vector<string> ip;
    vector<string> restoreIpAddresses(string s) {
        if(s.length() > 16) return res;
        backtracking(s, 0);
        return res;
    }

    void backtracking(string s, int startIndex) {
        if(ip.size() > 4) return;
        if (startIndex == s.length() && ip.size() == 4) {
            string tmp = ip[0];
            for (int i = 1; i < 4; i ++) {
                tmp += "." + ip[i];
            }
            res.push_back(tmp);
            return ;
        }
        for (int i = startIndex; i < s.length(); i++) {
            string substr = s.substr(startIndex, i - startIndex + 1);
            if(substr.length() > 1 && substr[0] == '0' || substr.length() > 3) break;
            int subnum = toInt(substr);
            if (subnum >= 0 && subnum <= 255) {
                ip.push_back(substr);
                backtracking(s, i + 1);
            }
            else break;
            ip.pop_back();
        }
    }

    int toInt(string str) {
        int res = 0;
        for (int i = 0; i < str.length(); i ++) {
            res = res * 10 + str[i] - '0';
        }
        return res;
    }
};

子集

https://leetcode-cn.com/problems/subsets/

怎么说，就很简单

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmpres;
    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums, 0);
        return res;
    }

    void backtracking(vector<int>& nums, int startIndex) {
        res.push_back(tmpres);
        for (int i = startIndex ; i < nums.size(); i ++) {
            tmpres.push_back(nums[i]);
            backtracking(nums, i + 1);
            tmpres.pop_back();
        }
        return ;
    }
};

子集Ⅱ※

https://leetcode-cn.com/problems/subsets-ii/

这个区别是nums数组中有重复元素了，那么这样就又可能选到重复的子集，那么这种重复是之前遇到的，在回溯的树形结构中，同一层如果出现同一元素，那么结果必然会有重复的，因此需要去掉同层之间的重复元素，所以去重的方法就是在每一层递归中记录一下遍历过的元素，如果下一个元素已经遍历过了那么就直接跳过。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmpres;
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        backtracking(nums, 0);
        return res;
    }

    void backtracking(vector<int>& nums, int startIndex) {
        res.push_back(tmpres);
        map<int, bool> flag;
        for (int i = startIndex ; i < nums.size(); i ++) {
            if (flag[nums[i]] == 0) {
                flag[nums[i]] = 1;
                tmpres.push_back(nums[i]);
                backtracking(nums, i + 1);
                tmpres.pop_back();
            }
        }
    }
};

递增子序列

https://leetcode-cn.com/problems/increasing-subsequences/

就很简单

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmpres;
    vector<vector<int>> findSubsequences(vector<int>& nums) {
        backtracking(nums, 0);
        return res;
    }

    void backtracking(vector<int>& nums, int startIndex) {
        if (tmpres.size() > 1) {
            res.push_back(tmpres);
        }
        map<int, bool> flag;
        for (int i = startIndex; i < nums.size(); i++) {
            if (flag[nums[i]] != 1) {
                if (tmpres.size() == 0 || nums[i] >= tmpres[tmpres.size() - 1]) {
                    tmpres.push_back(nums[i]);
                    flag[nums[i]] = 1;
                    backtracking(nums, i + 1);
                }
                else continue;
                tmpres.pop_back();
            }
        }
    }
};

全排列

https://leetcode-cn.com/problems/permutations/

像这种去重就是一个树枝上的重复元素，需要一个全局的标记，如果某个元素已经选上了，那么就不能再用了，即一个元素只能被选一次。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmpres;
    map<int, bool> flag;
    vector<vector<int>> permute(vector<int>& nums) {
        backtracking(nums);
        return res;
    }

    void backtracking(vector<int>& nums) {
        if (tmpres.size() == nums.size()) {
            res.push_back(tmpres);
            return ;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (flag[nums[i]] != 1) {
                flag[nums[i]] = 1;
                tmpres.push_back(nums[i]);
                backtracking(nums);
                tmpres.pop_back();
                flag[nums[i]] = 0;
            }
        }
    }
};

全排列Ⅱ※

https://leetcode-cn.com/problems/permutations-ii/submissions/

这道题中，数组出现了重复元素，也就是说同层之间需要去除重复值元素，一个子树中要去除同一个下标元素(一个下标只能被选一次)

class Solution {
public:
    vector<vector<int>> res;
    vector<int> tmpres;
    map<int, bool> flag;
    vector<vector<int>> permute(vector<int>& nums) {
        backtracking(nums);
        return res;
    }

    void backtracking(vector<int>& nums) {
        if (tmpres.size() == nums.size()) {
            res.push_back(tmpres);
            return ;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (flag[nums[i]] != 1) {
                flag[nums[i]] = 1;
                tmpres.push_back(nums[i]);
                backtracking(nums);
                tmpres.pop_back();
                flag[nums[i]] = 0;
            }
        }
    }
};

重新安排行程※

https://leetcode-cn.com/problems/reconstruct-itinerary/

一顿操作猛如虎，一看击败百分五

这道题有些难度，主要是怎么将tickets转换成比较容易计算判断的数据结构，可以直接用unordered_map<string, map<string, int>表示从源到目的机票数量，利用map的自动排序可以完成题目要求的字典顺序。

基本思路就是每到达一个地方就查看可以前往下一个地方的所有车票，因为用map存储，所以是按照字典序排列好的，用过的车票不能再用，所以需要将车票数量减1。

class Solution {
public:
    vector<string> tmpans;
    unordered_map<string, map<string, int>> mytickets;
    vector<string> findItinerary(vector<vector<string>>& tickets) {
        
        for (int i = 0; i < tickets.size(); i++ ) {
            mytickets[tickets[i][0]][tickets[i][1]] ++ ;
        }
        tmpans.push_back("JFK");
        backtracking(tickets, "JFK");

        return tmpans;
    }

    void backtracking(vector<vector<string>> tickets, string current) {
        if (tmpans.size() == tickets.size() + 1) return ;

        for (auto it = mytickets[current].begin(); it != mytickets[current].end() ; it ++) {
            if (it->second > 0) {
                it->second --;
                tmpans.push_back(it->first);
                backtracking(tickets, it->first);
                if (tmpans.size() == tickets.size() + 1) return ;
                tmpans.pop_back();
                it->second ++;
            }
            
        }

    }
};

n皇后※

https://leetcode-cn.com/problems/n-queens/

一顿操作...

如果一个点有皇后，那么它的该行、该列、对角行和饭对角行都不能有皇后，难点就在于怎么去表示i行j列这个点所影响的行列和对角。

这里需要用四个数组分别表示i行j列所在的行、列、对角行、反对角行：

以第i行、第j列为例：

  • row[i]
  • col[j]
  • xie[n-(i-j)-1]
  • backxie[i+j]

简单推以下就能得出。

class Solution {
public:
    vector<vector<string>> res;
    vector<string> tmpres;
    vector<vector<string>> solveNQueens(int n) {
        vector<int> row(n, 0);
        vector<int> col(n, 0);
        vector<int> xie(2 * n - 1, 0);
        vector<int> backxie(2 * n - 1, 0);
        string tmp = "";
        for (int i = 0; i < n; i ++) {
            tmp += '.';
        }
        for (int i = 0; i < n; i ++) {
            tmpres.push_back(tmp);
        }
        backtracking(n, row, col, xie, backxie, 0, 0);
        
        return res;

    }

    void backtracking(int n, vector<int>& row, vector<int>& col, vector<int>& xie, vector<int> backxie, int k, int cnt) {
        if (cnt == n) {
            res.push_back(tmpres);
            return ;
        }

        for (int i = k; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(row[i] != 1 && col[j] != 1 && xie[n - (i - j) - 1] != 1 && backxie[i + j] != 1) {
                    row[i] = 1;
                    col[j] = 1;
                    xie[n - (i - j) - 1] = 1;
                    backxie[i + j] = 1;
                    tmpres[i][j] = 'Q';
                    backtracking(n, row, col, xie, backxie, i + 1, cnt + 1);
                    tmpres[i][j] = '.';
                    row[i] = 0;
                    col[j] = 0;
                    xie[n - (i - j) - 1] = 0;
                    backxie[i + j] = 0;
                }
            }
           
        }
    }
};

解数独

https://leetcode-cn.com/problems/sudoku-solver/

这个相比于N皇后问题，不同点在于：

  • 只有一个解，所以回溯函数一旦找到解之后就应该立即返回，因此递归的出口需要写清楚
  • 从一个皇后升级到了9个不同的皇后
func solveSudoku(board [][]byte)  {
    var numrow [9][10] int
    var numcol [9][10] int
    var num9 [9][10] int
    var backtracking func(board [][]byte) int 

    for i := 0; i < 9; i++ {
        for j := 0; j < 9; j++ {
            if board[i][j] != '.' {
                numrow[i][board[i][j] - '0'] = 1
                numcol[j][board[i][j] - '0'] = 1
                num9[i / 3 * 3 + j / 3][board[i][j] - '0'] = 1
                continue
            }
        }
    }
    
    backtracking = func(board [][]byte) int {
        for i := 0; i < 9; i++ {
            for j := 0; j < 9; j++ {
                if board[i][j] == '.' {
                    for k := 1; k <= 9; k++ {
                        if numrow[i][k] == 0 && numcol[j][k] == 0 && num9[i / 3 * 3 + j / 3][k] == 0 {
                            numrow[i][k] = 1
                            numcol[j][k] = 1
                            num9[i / 3 * 3 + j / 3][k] = 1
                            board[i][j] = byte(k + '0')
                            if backtracking(board) == 1 {
                                return 1
                            }
                            numrow[i][k] = 0
                            numcol[j][k] = 0
                            num9[i / 3 * 3 + j / 3][k] = 0
                            board[i][j] = '.'
                        }
                    }
                    return 0
                }
            }
        }
        return 1
    }
    backtracking(board)
}
【算法】贪心 上一篇
同时安装python2(pip2)和python3(pip3) 下一篇
0%