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

---

一、全排列

1、题目描述

leetcode链接

2、代码

class Solution 
{
public:
    // 全局变量
    vector<vector<int>> ret;
    vector<int> path;
    bool check[7]; // 该题目最大到6--用以判断每个字符的使用情况
    vector<vector<int>> permute(vector<int>& nums) 
    {
        dfs(nums);
        return ret;
    }
    void dfs(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;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

3、解析

二、子集

1、题目描述

leetcode链接

2、代码

代码1：

class Solution 
{
public:
    // 全局变量
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        dfs(nums, 0);
        return ret;
    }
    void dfs(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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

代码2：

class Solution 
{
public:
    // 全局变量
    vector<vector<int>> ret;
    vector<int> path;
    vector<vector<int>> subsets(vector<int>& nums) 
    {
        dfs(nums, 0);
        return ret;
    }
    void dfs(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(); // 恢复现场
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3、解析

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

1、题目描述

leetcode链接

2、代码

class Solution 
{
public:
    // 1、全局变量
    int sum = 0; // 记录最终结果
    int path = 0; // 记录当前异或后的值
    int subsetXORSum(vector<int>& nums) 
    {
        dfs(nums, 0);
        return sum;
    }
    // 2、递归
    void dfs(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];
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

3、解析

四、全排列II

1、题目解析

leetcode链接

2、代码

代码1：

class Solution 
{
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;
    }
    void dfs(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;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

代码2：

class Solution 
{
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;
    }
    void dfs(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;
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

3、解析

五、电话号码的字母组合

1、题目描述

leetcode链接

2、代码

class Solution 
{
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;
    }
    void dfs(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(); // 恢复现场
        }
    } 
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

3、解析