[数据结构与算法]LeetCode-＞深度优先搜索专题

回溯->后悔药（找完后回头）
1、终止条件
2、递归公式
放进去一个元素
执行递归公式
撤回这个元素

搜索的设计：每一层递归都尝试搜索一部分的解空间
递归的状态：区别不同的递归，如何知道现在搜索到了哪里，每一层递归的内容都是固定的，通过参数信息来区分，通过当前参数的信息来区分目前搜索到了哪里。递归过程中状态可能互相影响，通过回溯解决
递归的结束条件：1、找到可行性解。2、搜索完毕

// 1、需要全部答案的路径
vector<类型> res; // 最终答案

void backtrack(res, 临时路径, 输入) {
    结束条件:
        临时路径，新增一个路径
            
    循环：(每次选择一个数据进行下一次的递归) // 每一个都可能是起点
        选择一个数据 (每次循环，浅层的逻辑：选择其它数据)
        backtrack(res, 临时路径, 输入)
        撤回选择的数据
}

// 2、不需要全部路径，只需要true或false

46 全排列
题型：区间中不包含重复数字的全排列
排列问题和组合问题的区别：排列问题加上了顺序的概念，例如：[1,2,3]和[1, 3, 2]是不一样的，但是对于组合问题来说这俩是一样的。所以排列问题在搜索的过程中，需要重新审视整个区间，并且把没有选过的元素，重新选择。

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        dfs(nums, used);
        return res;
    }

    void dfs(vector<int>& nums, vector<bool>& used)
    {
        if (path.size() == nums.size())
        {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i ++)
        {
            if (!used[i])
            {
                used[i] = true;
                path.push_back(nums[i]);
                dfs(nums, used);
                path.pop_back();
                used[i] = false;
            }
        }
    }
};

47 全排列II
题型：区间中包含重复数字的全排列
排序
注意：!used[i - 1]

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<bool> used(nums.size(), false);
        sort(nums.begin(), nums.end());
        dfs(nums, used);
        return res;
    }

    void dfs(vector<int> &nums, vector<bool>& used)
    {
        if (path.size() == nums.size())
        {
            res.push_back(path);
            return;
        }

        for (int j = 0; j < nums.size(); j ++)
        {
            if (j > 0 && nums[j] == nums[j - 1] && !used[j - 1]) continue;
            if (!used[j])
            {
                used[j] = true;
                path.push_back(nums[j]);
                dfs(nums, used);
                path.pop_back();
                used[j] = false;
            }
        }
    }
};

组合问题
77 组合
题型：区间中没有重复元素，每个元素只能选一次

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

    void dfs(int l, int r, int k)
    {
        if (k == 0)
        {
            res.push_back(path);
        }

        for (int i = l; i <= r; i ++)
        {
            path.push_back(i); // 取当前值，然后下一步继续往后找下一个值（取了当前，再往后取），进for前面的
            dfs(i + 1, r, k - 1);
            path.pop_back(); // 不取当前值，然后往后找下一个值（取后面的），走for后面的
        }
    }
};

39 组合总和
题型：区间中没有重复元素，但是每个元素可以无限制重复使用
无重复元素，每个数可重复使用。找到全部的不同组合，以列表形式方式，以任意顺序(不用考虑顺序问题)
两数之和题目：找到一个，然后返回其索引值

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        int n = candidates.size();
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0, 0);
        return res;
    }

    void dfs(vector<int>& candidates, int target, int i, int sum)
    {
        if (sum > target) return;
        if (sum == target) res.push_back(path);

        for (int j = i; j < candidates.size(); j ++)
        {
            int t = candidates[j];
            if (sum + t > target) continue;
            path.push_back(t);
            sum += t;
            dfs(candidates, target, j, sum);
            path.pop_back();
            sum -= t;
        }
    }
};

40 组合总和II
题型：区间中有重复数字，每个数字只能选择一次
去重：规定每次加入重复数字时，必须先加入下标小的重复数字才能继续加入下标大的重复数字，这样重复数字的相对顺序就是固定的
[10, 1, 2, 7, 6, 1, 5]：[1,7]和[7,1]是两个重复的组合
固定重复数字的相对顺序，通过对数组排序，使重复数字排在一起，每次添加数字时，判断当前数字是否与前面的数字相同，如果相同且前面的数字还没有添加到当前路径即下标下的重复数字未添加则忽略

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<bool> used(candidates.size(), false);
        sort(candidates.begin(), candidates.end());
        dfs(candidates, target, 0, 0, used);
        return res;
    }

    void dfs(vector<int>& candidates, int target, int i, int sum, vector<bool> used)
    {
        if (sum > target) return;
        if (sum == target)
        {
            res.push_back(path);
            return;
        }

        for (int j = i; j < candidates.size(); j ++)
        {
            if (j > 0 && candidates[j] == candidates[j - 1] && !used[j - 1]) continue;
            int t = candidates[j];
            if (sum + t > target) continue;
            path.push_back(t);
            used[j] = true;
            sum += t;
            dfs(candidates, target, j + 1, sum, used);
            path.pop_back();
            used[j] = false;
            sum -= t;
        }
    }
};

17 电话号码的字母组合
字母和数字的对应

class Solution {
public:
    // 么个数字对应的字母集合
    string letterMap[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    };
    vector<string> res;
    string str;

    void backtracking(string& digits, int index) { // index遍历字符串
        if (index == digits.size()) {
            res.push_back(str);
            return;
        }
        int t = digits[index] - '0';
        string letters = letterMap[t];
        for (int i = 0; i < letters.size(); i ++) {
            str.push_back(letters[i]);
            backtracking(digits, index + 1);
            str.pop_back();
        }
    }

    vector<string> letterCombinations(string digits) {
        if (digits.size() == 0) return res;
        backtracking(digits, 0);
        return res;
    }
};

78 子集
搜集所有中间的状态，不用判断终止条件，因为所有情况都需要搜集

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

    void dfs(vector<int>& nums, int i)
    {
        res.push_back(path);
        for (int j = i; j < nums.size(); j ++)
        {
            path.push_back(nums[j]);
            dfs(nums, j + 1);
            path.pop_back();
        }
    }
};

131 分割回文串
题型：本质上还是组合问题

class Solution {
public:
    vector<vector<string>> res;
    vector<string> path;
    vector<vector<string>> partition(string s) {
        dfs(s, 0);
        return res;
    }

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

    void dfs(string& s, int i)
    {
        if (i == s.size())
        {
            res.push_back(path);
            return;
        }
        for (int j = i; j < s.size(); j ++)
        {
            if (!isPalindrome(s, i, j)) continue;
            path.push_back(s.substr(i, j - i + 1));
            dfs(s, j + 1);
            path.pop_back();
        }
    }
};

79 单词搜索
怎么搜一个路径：先枚举起点，然后再枚举每一个的方向，对每个方向都递归下去

class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        for (int i = 0 ; i < board.size(); i ++)
        {
            for (int j = 0; j < board[i].size(); j ++)
            {
                if (dfs(board, word, 0, i, j)) return true;
            }
        }
        return false;
    }

    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1}; // 上右下左四个方向
    bool dfs(vector<vector<char>>& board, string& word, int u, int x, int y)
    {
        if (board[x][y] != word[u]) return false;
        if (u == word.size() - 1) return true;

        char t = board[x][y]; // 存一下当前字符，为了回溯用
        board[x][y] = '.';
        for (int i = 0; i < 4; i ++)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= board.size() || b < 0 || b >= board[0].size() || board[a][b] == '.') continue;
            if (dfs(board, word, u + 1, a, b)) return true;
        }
        // 枚举完当前点的三个方向，枚举的时候这个点都是被标记的
        board[x][y] = t; // 回溯
        return false;
    }
};

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖