Leetcode by chgkn - 14. 回溯 - 《Chgkn's Notebook》

参考

回溯套路

解决一个回溯问题，实际上就是一个决策树的遍历过程。需要思考三个问题：

1.路径: 也就是已经做出的选择； 2.选择列表：也就是你当前可以做的选择； 3.结束条件：也就是达到决策树底层，无法再做出选择的条件。

res = []
def backtrack(path, candidate):
    if is border:
        res.append(path)
        return
       for select in candidate:
        # make select
        将选择从选择列表中移除
        path.append(选择)
        backtrack(path, candidate)
        # cancle select
        path.remove(选择)
        将选择再加入选择列表

Q46. 全排列 MEDIUM

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

只要从根遍历这棵树，记录路径上的数字，其实就是所有的全排列。我们不妨把这棵树称为回溯算法的「决策树」。
现在可以解答开头的几个名词：[2]就是「路径」，记录你已经做过的选择；[1,3]就是「选择列表」，表示你当前可以做出的选择；「结束条件」就是遍历到树的底层，在这里就是选择列表为空的时候

我们定义的backtrack函数其实就像一个指针，在这棵树上游走，同时要正确维护每个节点的属性，每当走到树的底层，其「路径」就是一个全排列。

如何遍历一棵树？
各种搜索问题其实都是树的遍历问题，而多叉树的遍历框架就是这样：

void traverse(TreeNode *root)
{
    for (TreeNode child:root->children)
        // 前序遍历操作
        traverse(child);
        // 后续遍历操作
}

其中前序遍历和后续遍历是两个很有用的时间点

前序遍历的代码在进入某一个节点之前的那个时间点执行，后序遍历代码在离开某个节点之后的那个时间点执行。
回想我们刚才说的，「路径」和「选择」是每个节点的属性，函数在树上游走要正确维护节点的属性，那么就要在这两个特殊时间点搞点动作：

我们只要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径。

class Solution {
public:

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> track{};
        backtrack(nums,track,res);
        return res;
    }
    void backtrack(vector<int>& nums,vector<int>& track,vector<vector<int>>&res)
    {
        // 边界条件
        if (track.size()==nums.size()) 
        {
            res.push_back(track);return;
        }
        for(int i =0;i<nums.size();i++)
        {
            if (find(track.begin(),track.end(),nums[i])!=track.end())
            {
                continue;
            }
            track.push_back(nums[i]);
            backtrack(nums,track,res);
            track.pop_back();
        }
    }
};

47. 全排列 II MEDIUM

给定一个可包含重复数字的序列，返回所有不重复的全排列。示例:

输入: [1,1,2]

输出:

[

[1,1,2],

[1,2,1],

[2,1,1]

]

通过次数75,659提交次数127,167

class Solution {
public:
    vector<vector<int>> res;
    vector<int> track;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        vector<int>visited(nums.size());
        backtrack(nums,0,visited);
        return res;
    }
    void backtrack(vector<int>& nums,int n,vector<int>&visited)
    {
        if (n==nums.size()) 
        {
            res.push_back(track);
            return;
        }
        for(int i =0;i<nums.size();i++)
        {
            //如果这个数和之前的数一样，并且之前的数还未使用过（说明已经回溯过）
            // 因为前面的数肯定再遍历的时候有visited[i]==1,回溯时才被撤销选择visited = 0
            // 这里面将路径表示为n（节点数）和visited（是否被遍历回溯）以及track
            if (visited[i] == 0)
            {
                if (i>=1 && nums[i]==nums[i-1] && visited[i-1]!=0) continue;
                track.push_back(nums[i]);
                visited[i] =1;
                backtrack(nums,n+1,visited);
                visited[i]= 0;
                track.pop_back();
            }
        }
    }
};

Q10. 正则表达式匹配 HARD

动态规划做法Q10. 正则表达式匹配

Q22. 括号生成 MEDIUM

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

示例：

输入：n = 3

输出：[
   "((()))",

   "(()())",

   "(())()",

   "()(())",

   "()()()"

 ]
通过次数156,987提交次数206,836

class Solution {
public:
    vector<string> res;
    vector<string> generateParenthesis(int n) {
        backtrack(n,n,"");
        return res;
    }
    void backtrack(int l,int r,string track)
    {
        if(l==0&&r==0) 
        {
            res.push_back(track);
            return;
        }

        if (l>0)
        {
            backtrack(l-1,r,track+'(');

        }
        if(r>l ) // 有左括号先被使用才能使用右括号
        {
            backtrack(l,r-1,track+')');
        }

    }
};