回溯主要解决一些暴力枚举也搞不定的问题，例如组合、分割、子集、排列，棋盘等。这一关我们就看几个例子。

关卡名	回溯热门问题	我会了✔️
内容	1. 组合总和问题	✔️
	2. 分割回文串问题	✔️
	3. 子集问题	✔️
	4. 排列问题	✔️
	5. 字母全排列问题	✔️
	6. 单词搜索	✔️

1. 组合总问题

LeetCode39题目要求：给你一个无重复元素的整数数组candidates和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同组合 ，并以列表形式返回。你可以按任意顺序返回这些组合。 candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 数组中的元素满足1 <= candidates[i] <= 200。例子：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意2可以使用多次。
7 也是一个候选， 7 = 7 ，仅有这两种组合。

如果不考虑重复，本题与LeetCode113题就是一个题，如果可以重复，那是否会无限制取下去呢？也不会，因为题目给了说明，每个元素最小为1，因此最多也就target个1。 我们画图看该怎么做，对于序列{2,3,6,7}，target=7。很显然我们可以先选择一个2，然后剩下的target就是7-2=5。再选一个2，剩余5-2=3。之后再选一个2，剩余3-2=1。已经小于2了，我们不能继续向下了，要返回一下。看看有没有3。OK，序列中有3，那么就得到了第一个结果{2,2,3}。 之后我们继续回退到只选了一个2的时候，这时候不能再取2了，而是从{3,6,7}中选择，如下图所示，没有符合要求的！ 依次类推，后面尝试从3、6和7开始选择。 所以我们最终得到的结果就是{2,2,3}和{2,5}。为了方便，我们可以先对元素做个排序，然后将上面的过程画成这个一个树形图：

这个图横向是针对每个元素的暴力枚举，纵向是递归，也是一个纵横问题，实现代码也不复杂：

class CombinationSum {
    List<List<Integer>> res = new ArrayList<>(); //记录答案
    List<Integer> path = new ArrayList<>();  //记录当前正在访问的路径
 
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates,0, target);
        return res;
    }
    public void dfs(int[] c, int u, int target) {
        if(target < 0){
           return ;
        } 
        if(target == 0)
        {
            res.add(new ArrayList(path));
            return ;
        }
        for(int i = u; i < c.length; i++){
            if( c[i] <= target)  
            {
                path.add(c[i]);
               //当前层将target减掉了一部分，也就是子结构只要找是否有满足(target -  c[i])就可以了
                dfs(c,i,target -  c[i]); // 因为可以重复使用，所以还是i
                path.remove(path.size()-1); //回溯
            }
        }
    }
}

如果用Python，代码会简洁很多：

def combinationSum(self, candidates, target) :
        res = []
        path = []
        def backtrack(candidates,target,sum,startIndex):
            if sum > target: return 
            if sum == target: return res.append(path[:])
            for i in range(startIndex,len(candidates)):
                #如果 sum + candidates[i] > target 就终止遍历
                if sum + candidates[i] >target: return  
                sum += candidates[i] 
                path.append(candidates[i])
                #startIndex = i:表示可以重复读取当前的数
                backtrack(candidates,target,sum,i)  
                sum -= candidates[i]  #回溯
                path.pop()  #回溯
        candidates = sorted(candidates)  #需要排序
        backtrack(candidates,target,0,0)
        return res

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> res;
    vector<int> path;
    dfs(candidates, 0, target, res, path);
    return res;
}

void dfs(vector<int>& c, int u, int target, vector<vector<int>>& res, vector<int>& path) {
    if (target < 0) {
        return;
    }
    if (target == 0) {
        res.push_back(path);
        return;
    }
    for (int i = u; i < c.size(); i++) {
        if (c[i] <= target) {
            path.push_back(c[i]);
            dfs(c, i, target - c[i], res, path);
            path.pop_back(); // 回溯，弹出当前节点
        }
    }
}

2. 分割回文串问题

分割问题也是回溯要解决的典型问题之一，常见的题目有分割回文串、分割IP地址，以及分割字符串等。 LeetCode131 分割回文串，给你一个字符串s，请你将s分割成一些子串，使每个子串都是回文串 ，返回s所有可能的分割方案。 回文串是正着读和反着读都一样的字符串。

示例1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

字符串如何判断回文本身就是一个道算法题，本题在其之上还要再解决一个问题：如何切割？如果暴力切割，是非常困难的，如果从回溯的角度来思考就清晰很多：

我们说回溯本身仍然会进行枚举，这里的也一样。切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。这里就是先试一试,第一次切'a',第二次切'aa',第三次切'aab'。这对应的就是回溯里的for循环，也就是横向方面。 我们还说回溯仍然会进行递归，这里也是一样的，第一次切了'a',剩下的就是'ab'。递归就是再将其再切一个回文下来，也就是第二个'a',剩下的'b'再交给递归进一步切割。这就是纵向方面要干的事情，其他以此类推。 至于回溯操作与前面是一样的道理，不再赘述。通过代码就可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

class Partition {
    List<List<String>> lists = new ArrayList<>();
    Deque<String> deque = new LinkedList<>();
 
    public List<List<String>> partition(String s) {
        backTracking(s, 0);
        return lists;
    }
 
    private void backTracking(String s, int startIndex) {
        //如果起始位置大于s的大小，说明找到了一组分割方案
        if (startIndex >= s.length()) {
            lists.add(new ArrayList(deque));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            //如果是回文子串，则记录
            if (isPalindrome(s, startIndex, i)) {
                String str = s.substring(startIndex, i + 1);
                deque.addLast(str);
            } else {
                continue;
            }
            //起始位置后移，保证不重复
            backTracking(s, i + 1);
            deque.removeLast();
        }
    }
    //判断是否是回文串
    private boolean isPalindrome(String s, int startIndex, int end) {
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

class Partition:
    def __init__(self):
        self.paths = []
        self.path = []

    def partition(self, s) :
        '''
        当切割线迭代至字符串末尾，说明找到一种方法
        类似组合问题，为了不重复切割同一位置，需要start_index来做标记下一轮递归的起始位置(切割线)
        '''
        self.path.clear()
        self.paths.clear()
        self.backtracking(s, 0)
        return self.paths

    def backtracking(self, s: str, start_index: int) -> None:
        # Base Case
        if start_index >= len(s):
            self.paths.append(self.path[:])
            return

        # 单层递归逻辑
        for i in range(start_index, len(s)):
            # 此次比其他组合题目多了一步判断：
            # 判断被截取的这一段子串([start_index, i])是否为回文串
            if self.is_palindrome(s, start_index, i):
                self.path.append(s[start_index:i+1])
                self.backtracking(s, i+1)   # 递归纵向遍历：从下一处进行切割，判断其余是否仍为回文串
                self.path.pop()             # 回溯
            else:
                continue    

    def is_palindrome(self, s: str, start: int, end: int) -> bool:
        i: int = start        
        j: int = end
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True

bool isPalindrome(string s, int startIndex, int end) {
    for (int i = startIndex, j = end; i < j; i++, j--) {
        if (s[i] != s[j]) {
            return false;
        }
    }
    return true;
}

void backTracking(string s, int startIndex, vector<vector<string>>& lists, stack<string>& deque) {
    if (startIndex >= s.length()) {
        lists.push_back(deque.empty() ? vector<string>() : std::vector<string>(deque.top()));
        deque.pop();
        return;
    }
    for (int i = startIndex; i < s.length(); i++) {
        if (isPalindrome(s, startIndex, i)) {
            string str = s.substr(startIndex, i - startIndex + 1);
            deque.push(str);
        } else {
            continue;
        }
        backTracking(s, i + 1, lists, deque);
        deque.pop();
    }
}


vector<vector<string>> partition(string s) {
    vector<vector<string>> lists;
    stack<string> deque;
    backTracking(s, 0, lists, deque);
    return lists;
}

3. 子集问题

子集问题也是回溯的经典使用场景。回溯可以画成一种树状结构，子集、组合、分割问题都可以抽象为一棵树，但是子集问题与其他的类型有个明显的区别，组合问题一般找到满足要求的结果即可，而集合则要找出所有的情况。 LeetCode78，给你一个整数数组nums，数组中的元素互不相同。返回该数组所有可能的子集（幂集）。解集不能包含重复的子集。你可以按任意顺序返回解集。

示例1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

看上面的例子nums = [1,2,3]，将子集抽象为树型结构如下：

从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。 这里什么时候要停下来呢？其实可以不加终止条件，因为startIndex >= nums.size()，本层for循环本来也结束了。 而且求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。这样实现起来也比较容易。

class Subsets {
// 存放符合条件结果的集合
    List<List<Integer>> result = new ArrayList<>();
// 用来存放符合条件结果
    LinkedList<Integer> path = new LinkedList<>();
    public List<List<Integer>> subsets(int[] nums) {
         //空集合也是一个子集
        if (nums.length == 0){
            result.add(new ArrayList<>());
            return result;
        }
        subsetsHelper(nums, 0);
        return result;
    }
 
    private void subsetsHelper(int[] nums, int startIndex){
//「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。
        result.add(new ArrayList<>(path));
        if (startIndex >= nums.length){ 
            return;
        }
        for (int i = startIndex; i < nums.length; i++){
            path.add(nums[i]);
            subsetsHelper(nums, i + 1);
            path.removeLast();
        }
    }
}

class Subsets:
    def __init__(self):
        self.path: List[int] = []
        self.paths: List[List[int]] = []

    def subsets(self, nums) :
        self.paths.clear()
        self.path.clear()
        self.backtracking(nums, 0)
        return self.paths

    def backtracking(self, nums, start_index) :
        # 收集子集，要先于终止判断
        self.paths.append(self.path[:])
        # Base Case
        if start_index == len(nums):
            return

        # 单层递归逻辑
        for i in range(start_index, len(nums)):
            self.path.append(nums[i])
            self.backtracking(nums, i+1)
            self.path.pop()     # 回溯

class Subsets {
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
        if (startIndex >= nums.size()) { // 终止条件可以不加
            return;
        }
        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear();
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

上面代码里定义了全局变量result和path，这样整体比较简洁。这里可以转换成方法参数的形式，只是看起来比较复杂一些。

4. 排列问题

LeetCode46.给定一个没有重复数字的序列，返回其所有可能的全排列。例如： 排列问题是典型的小学生都会，但是难道众人的问题。这个问题与前面组合等问题的一个区别是使用过的后面还要再用，例如1，在开始使用了，但是到了2 和3的时候仍然要再使用一次。这本质上是因为 [1,2] 和 [2,1] 从集合的角度看是一个，但从排列的角度看是两个。 元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次，所以就不能使用startIndex了，为此可以使用一个used数组来标记已经选择的元素，完整过程如图所示:

这里的终止条件怎么判断呢？从上图可以看出叶子节点就是结果。那什么时候是到达叶子节点呢？ 当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

class Permute {
    List<List<Integer>> result = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        if (nums.length == 0){
            return result;
        }
        used = new boolean[nums.length];
        permuteHelper(nums);
        return result;
    }
 
    private void permuteHelper(int[] nums){
        if (path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++){
            if (used[i]){
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            permuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

class Permute:
    def __init__(self):
        self.path = []
        self.paths = []

    def permute(self, nums) :
        '''
        因为本题排列是有序的，这意味着同一层的元素可以重复使用，但同一树枝上不能重复使用(usage_list)
        所以处理排列问题每层都需要从头搜索，故不再使用start_index
        '''
        usage_list = [False] * len(nums)
        self.backtracking(nums, usage_list)
        return self.paths

    def backtracking(self, nums, usage_list) :
        # Base Case本题求叶子节点
        if len(self.path) == len(nums):
            self.paths.append(self.path[:])
            return

        # 单层递归逻辑
        for i in range(0, len(nums)):  # 从头开始搜索
            # 若遇到self.path里已收录的元素，跳过
            if usage_list[i] == True:
                continue
            usage_list[i] = True
            self.path.append(nums[i])
            self.backtracking(nums, usage_list)     # 纵向传递使用信息，去重
            self.path.pop()
            usage_list[i] = False

class Permute {
    vector<vector<int>> result;
    vector<int> path;
    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++) {
            if (used[i] == true) continue; // path里已经收录的元素，直接跳过
            used[i] = true;
            path.push_back(nums[i]);
            backtracking(nums, used);
            path.pop_back();
            used[i] = false;
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);
        backtracking(nums, used);
        return result;
    }
};

5. 字母全排列问题

LeetCode784. 字母大小写全排列：给定一个字符串 s ，通过将字符串 s 中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。以任意顺序返回输出。

示例1：输入：s = "a1b2"
输出：["a1b2", "a1B2", "A1b2", "A1B2"]

如果本题去掉数字，只告诉你两个字母ab，让你每个字母变化大小写，那就是ab、Ab、aB、AB四种情况，题目比2.6电话号码问题还简单，这里的数字就是干扰项，我们需要做的是过滤掉数字， 只处理字母。另外还要添加个大小写转换的问题。如下图所示：

由于每个字符的大小写形式刚好差了32，因此在大小写装换时可以用c⊕32 来进行转换和恢复。代码如下：

class LetterCasePermutation {
    public List<String> letterCasePermutation(String s) {
        List<String> ans = new ArrayList<String>();
        dfs(s.toCharArray(), 0, ans);
        return ans;
    }

    public void dfs(char[] arr, int pos, List<String> res) {
        while (pos < arr.length && Character.isDigit(arr[pos])) {
            pos++;
        }
        if (pos == arr.length) {
            res.add(new String(arr));
            return;
        }
        arr[pos] ^= 32;
        dfs(arr, pos + 1, res);
        arr[pos] ^= 32;
        dfs(arr, pos + 1, res);
    }
}

class LetterCasePermutation:
    def letterCasePermutation(self, s: str) -> List[str]:
        ans = []
        def dfs(s: List[str], pos: int) -> None:
            while pos < len(s) and s[pos].isdigit():
                pos += 1
            if pos == len(s):
                ans.append(''.join(s))
                return
            dfs(s, pos + 1)
            s[pos] = s[pos].swapcase()
            dfs(s, pos + 1)
            s[pos] = s[pos].swapcase()
        dfs(list(s), 0)
        return ans

class LetterCasePermutation {
public:
    void dfs(string &s, int pos, vector<string> &res) {
        while (pos < s.size() && isdigit(s[pos])) {
            pos++;
        }
        if (pos == s.size()) {
            res.emplace_back(s);
            return;
        }
        s[pos] ^= 32;
        dfs(s, pos + 1, res);
        s[pos] ^= 32;
        dfs(s, pos + 1, res);
    }

    vector<string> letterCasePermutation(string s) {
        vector<string> ans;
        dfs(s, 0, ans);
        return ans;
    }
};

6. 单词搜索

LeetCode79.给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

思路：从上到下，左到右遍历网格，每个坐标递归调用check(i, j, k)函数，i,j表示网格坐标，k表示word的第k个字符，如果能搜索到第k个字符返回true，否则返回false，check函数的终止条件有2种情况 1如果i，j位置的字符和字符串位置k的字符不相等，则这条搜索路径搜索失败 返回false 2如果搜索到了字符串的结尾，则找到了网格中的一条路径，这条路径上的字符正好可以组成字符串s 两种情况都不满足则把当前网格节点加入visited数组，visited表示节点已经访问过了，然后顺着当前网格坐标的四个方向继续尝试，如果没找到k开始的子串，则回溯状态visited[i] [j] = false，继续后面的尝试。 复杂度分析：时间复杂度O(MN⋅3^L)，M,N 为网格的长度与宽度，L 为字符串 word 的长度，第一次调用check函数的时候，进行4个方向的检查，其余坐标的节点都是3个方向检查，走过来的分支不会反方向回去，所以check函数的时间复杂度是3^L，而网格有M*N个坐标，且存在剪枝，所以最坏的情况下时间复杂度是O(MN⋅3^L)。空间复杂度是O(MN)，visited数组空间是O(MN)，check递归栈的最大深度在最坏的情况下是O(MN)

class Solution {
    public boolean exist(char[][] board, String word) {
        int h = board.length, w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                boolean flag = check(board, visited, i, j, word, 0);
                if (flag) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean check(char[][] board, boolean[][] visited, int i, int j, String s, int k) {
        if (board[i][j] != s.charAt(k)) {
            return false;
        } else if (k == s.length() - 1) {
            return true;
        }
        visited[i][j] = true;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        boolean result = false;
        for (int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            if (newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if (!visited[newi][newj]) {
                    boolean flag = check(board, visited, newi, newj, s, k + 1);
                    if (flag) {
                        result = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return result;
    }
}

class Exist:
    def exist(self, board, word) :
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
            if k == len(word) - 1: return True
            board[i][j] = ''
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            board[i][j] = word[k]
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0): return True
        return False

class Exist {
public:
bool exist(vector<vector<char>>& board, string word) {
    rows = board.size();
    cols = board[0].size();
    for(int i = 0; i < rows; i++) {
        for(int j = 0; j < cols; j++) {
            if (dfs(board, word, i, j, 0)) return true;
        }
    }
    return false;
}
private:
int rows, cols;
bool dfs(vector<vector<char>>& board, string word, int i, int j, int k) {
    if (i >= rows || i < 0 || j >= cols || j < 0 || board[i][j] != word[k]) return false;
    if (k == word.size() - 1) return true;
    board[i][j] = '\0';
    bool res = dfs(board, word, i + 1, j, k + 1) || dfs(board, word, i - 1, j, k + 1) || 
    dfs(board, word, i, j + 1, k + 1) || dfs(board, word, i , j - 1, k + 1);
    board[i][j] = word[k];
    return res;
}
};

7. 通关文牒

本文讲解了很多经典的回溯问题，将上面的内容理解清楚即可