回溯模板

回溯模板

//交换版
void backtrack(int index, vector<int> &s){
    if(/*满足的条件*/){
        /*加入结果*/
        return;
    }

    for(int i=index;i<s.size();i++){
        swap(s[i], s[index]);
        backtrack(index+1, s);
        swap(s[i], s[index]);
    }
}

//添加删除版
void backtrack(vector<int> &s, vector<int> &temp/*或者是string*/){
    if(/*满足的条件*/){
        /*加入结果*/
        return;
    }

    for(int i=index;i<s.size();i++){
        temp.push_back(s[i]);
        backtrack(s, temp);
        temp.pop_back();
    }
}

下面是上面两个模板的实例，两个方法通用
```c++
//全排列II  https://leetcode-cn.com/submissions/detail/163570148/
class Solution {
public:

    set<vector<int>> res;

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        backtrace(0,nums.size()-1, nums);
        return vector<vector<int>>(res.begin(), res.end());
    }

    void backtrace(int index, int n, vector<int>& nums){
        if(index==n){
            res.insert(nums);
            return;
        }

        for(int i=index;i<=n;i++){
            swap(nums[i], nums[index]);
            backtrace(index+1, n, nums);
            swap(nums[i], nums[index]);
        }
    }


};

//全排列  https://leetcode-cn.com/problems/permutations/
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> ans;
        backtrace(nums, res, ans);
        return res;
    }
    void backtrace(vector<int>& nums, vector<vector<int>>& res, vector<int>& ans)
    {
        /*满足结束条件*/
        if(ans.size()==nums.size()){
            res.push_back(ans);
            return ;
        }
        for(vector<int>::iterator it=nums.begin(); it != nums.end(); it++)
        {
            int x = *it;

            if(find(ans.begin(),ans.end(),x) != ans.end())//x在路径中，不考虑
            {
                continue;
            }
            ans.push_back(x);//选择x

            backtrace(nums, res, ans);//下一步

            ans.erase( ans.end()-1, ans.end() );//撤销选择
        }
        return ;
    }
};

当然对于树或者图的，遍历循环改成左右子树就可，下面是257.二叉树的所有路径

链接：https://leetcode-cn.com/problems/binary-tree-paths/solution/yi-pian-wen-zhang-jie-jue-suo-you-er-cha-5f58/

vector<string> res;
vector<string> binaryTreePaths(TreeNode<T> *root)
{
    dfs(root, "");
    return res;
}

void dfs(TreeNode*root, string path)
{
    if (!root)
        return;
    path += to_string(root->val);
    if (!root->left && !root->right)
    {
        res.push_back(path);
        return;
    }
    dfs(root->left, path+"->");
    dfs(root->right, path+"->");
}