【leetcode】深搜、暴搜、回溯、剪枝（C++）1

深搜、暴搜、回溯、剪枝（C++）1

一、全排列

1、题目描述

leetcode链接

2、代码

classSolution{public:// 全局变量
    vector<vector<int>> ret;
    vector<int> path;bool check[7];// 该题目最大到6--用以判断每个字符的使用情况
    vector<vector<int>>permute(vector<int>& nums){dfs(nums);return ret;}voiddfs(vector<int>& nums){// 递归出口if(nums.size()== path.size()){
            ret.push_back(path);return;}for(int i =0; i < nums.size(); i++){if(check[i]==false){
                path.push_back(nums[i]);
                check[i]=true;// 标记用过了dfs(nums);// 递归// 回溯
                path.pop_back();
                check[i]=false;}}}};

3、解析

二、子集

1、题目描述

leetcode链接

2、代码

代码1：

classSolution{public:// 全局变量
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>>subsets(vector<int>& nums){dfs(nums,0);return ret;}voiddfs(vector<int>& nums,int pos){// 1、递归出口if(pos == nums.size()){
            ret.push_back(path);return;}// 2、选
        path.push_back(nums[pos]);dfs(nums, pos +1);// 递归到下一层
        path.pop_back();// 恢复现场// 3、不选dfs(nums, pos +1);}};

代码2：

classSolution{public:// 全局变量
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>>subsets(vector<int>& nums){dfs(nums,0);return ret;}voiddfs(vector<int>& nums,int pos){// 1、递归出口
        ret.push_back(path);// 2、递归for(int i = pos; i < nums.size(); i++){
            path.push_back(nums[i]);dfs(nums, i +1);
            path.pop_back();// 恢复现场}}};

3、解析

三、找出所有子集的异或总和再求和

1、题目描述

leetcode链接

2、代码

classSolution{public:// 1、全局变量int sum =0;// 记录最终结果int path =0;// 记录当前异或后的值intsubsetXORSum(vector<int>& nums){dfs(nums,0);return sum;}// 2、递归voiddfs(vector<int>& nums,int pos){// 1、递归出口
        sum += path;// 2、往下递归for(int i = pos; i < nums.size(); i++){
            path ^= nums[i];dfs(nums, i +1);
            path ^= nums[i];}}};

3、解析

四、全排列II

1、题目解析

leetcode链接

2、代码

代码1：

classSolution{public:// 1、全局变量
    vector<vector<int>> ret;// 记录返回的数组
    vector<int> path;// 记录路径bool check[9];// 判断是否被使用过
    vector<vector<int>>permuteUnique(vector<int>& nums){// 2、排序sort(nums.begin(), nums.end());// 3、进行递归dfs(nums,0);return ret;}voiddfs(vector<int>& nums,int pos){// 1、递归出口if(pos == nums.size()){
            ret.push_back(path);return;}// 2、每一层的循环for(int i =0; i < nums.size(); i++){// 不合法情况进行剪枝if(check[i]==true||(i !=0&& nums[i]== nums[i -1]&& check[i -1]==false))continue;// path进行增加
            path.push_back(nums[i]);
            check[i]=true;// 递归dfs(nums, pos +1);// 回溯 -- 恢复现场
            path.pop_back();
            check[i]=false;}}};

代码2：

classSolution{public:// 1、全局变量
    vector<vector<int>> ret;// 记录返回的数组
    vector<int> path;// 记录路径bool check[9];// 判断是否被使用过
    vector<vector<int>>permuteUnique(vector<int>& nums){// 2、排序sort(nums.begin(), nums.end());// 3、进行递归dfs(nums,0);return ret;}voiddfs(vector<int>& nums,int pos){// 1、递归出口if(pos == nums.size()){
            ret.push_back(path);return;}// 2、每一层的循环for(int i =0; i < nums.size(); i++){// 不合法情况进行剪枝if(check[i]==false&&(i ==0|| nums[i]!= nums[i -1]|| check[i -1]==true)){// path进行增加
                path.push_back(nums[i]);
                check[i]=true;// 递归dfs(nums, pos +1);// 回溯 -- 恢复现场
                path.pop_back();
                check[i]=false;}}}};

3、解析

五、电话号码的字母组合

1、题目描述

leetcode链接

2、代码

classSolution{public:// 全局变量
    string hash[10]={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    string path;// 记录路径
    vector<string> ret;// 返回的组合
    vector<string>letterCombinations(string digits){if(digits.size()==0)return ret;dfs(digits,0);return ret;}voiddfs(string& digits,int pos){// 递归出口if(digits.size()== pos){
            ret.push_back(path);return;}// 循环找对应关系for(auto ch : hash[digits[pos]-'0'])// 掏出来字符串进行遍历当前下标所对应的字符串{// 尾插进去
            path.push_back(ch);dfs(digits, pos +1);
            path.pop_back();// 恢复现场}}};

3、解析