【算法】{画决策树 + dfs + 递归 + 回溯 + 剪枝} 解决排列、子集问题（C++）

1. 前言

1. dfs问题 我们已经学过，对于排列、子集类的问题，一般可以想到暴力枚举，但此类问题用暴力解法 一般都会超时，时间开销过大。
2. 对于该种问题，重点在于尽可能详细的 画决策树，随后根据决策树分析 题目所涉及的 剪枝、回溯、递归等细节问题。
3. 根据决策树的画法不同，题目会有不同的解法，只要保证决策树没有问题，保证细节问题下 代码一定可以编写出来。

2. 算法例题

46.全排列

思路

• 思路：求出数组中元素的所有排列顺序，并用数组输出。

• 解法一： 暴力枚举

  • 用n层for循环，每层循环依次固定一个数
  • 超时，时间开销太大，n个元素就是O(n ^ n)

• 解法二： 根据决策树 进行递归
  

  • 根据上图，我们需要创建下面三个全局变量.
    
  • 结束条件：当我们遍历到叶子节点时（即path.size() == nums.size()），将path加入到ret中，并向上返回。
  • 回溯：对当前元素dfs后，进行回溯，回溯即将之前加入到path 的元素删除，并将used重新置为false。

代码

class Solution {
public:
    vector<vector<int>> ret; // 用于存储最终结果
    bool used[7]; // 用于记录某个下标的元素是否在序列中
    vector<int> path; // 用于记录某个下标的元素是否已经加入到序列中
    vector<vector<int>> permute(vector<int>& nums) {
        dfs(nums);
        return ret;
    }

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

        // 遍历数组，对每一位都进行dfs && 排列
        for(int i = 0; i < nums.size(); ++i)
        {
            if(used[i] == false) // 如果该位置未加入到当前序列中
            {
                path.push_back(nums[i]);
                used[i] = true;
                dfs(nums);
                // dfs向上返回回来 -> 回溯
                path.pop_back();
                used[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

---

78.子集

• 题目要求我们将数组的所有子集统计，并以数组形式返回（空集就是空数组）

解法一

• 解法： 根据 选与不选 画决策树
  

  • 根据上图决策树，我们通过对一个元素的选择与否划分树，而当到达叶子节点的时候（i == nums.size()）向上返回即可。
  • 函数头：首先需要的参数是数组本身，其次我们通过变量i来标记当前选择的元素所在层数，则 void dfs(vector<int>& nums, int i)
  • 函数体：分别写出选择与不选择该元素时的代码即可
  • 结束条件：如前面所说，当 到叶子节点时返回。

代码

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

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

        // 不选当前元素
        dfs(nums, i + 1);

        // 选当前元素
        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
25
26
27

---

解法二

• 解法： 根据子集包含的元素个数 画 决策树
• 如上图所示，以此法画的决策树，每个节点的值都是有效值
  • 函数头：第一个参数是数组本身，另外需要给出当前遍历到nums的第几个元素。void dfs(vector<int>& nums, int pos)
  • 函数体：
    1. 在函数开始时先将当前子集加入到ret中
    2. 利用for循环，每次从pos开始遍历数组：每次将一个元素作为子集第一位的所有子集检索完毕后，再以下一个元素作为子集第一位，可以防止重复子集
       • for循环中每次将当前元素加入到path中，dfs下一位，最后回溯

代码

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

    void dfs(vector<int>& nums, int pos)
    {
        ret.push_back(path);
        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

有待更新… …