算法基础算法

常见的枚举方式

字数统计: 1.7k字   |   阅读时长: 9分
, , , ,

摘要: 本文梳理一下常见的枚举方式，以及对应的代码模板

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

枚举与分类讨论、找规律、按位单独处理、分别计算各元素贡献、逆向思维、惰性更新 等一样，也是一种思想或技巧，而很难归为某个具体算法。实践中需要再具体问题中灵活应用。

虽然这种思想性的东西在实际问题中的应用是很灵活的，但还是有一些套路性的东西的，本文就总结一下常见的枚举方式，并给出对应的代码模板。主要内容如下：

  • 多项式型枚举：欧式空间的坐标
  • 指数型枚举：子集
    • 无重
      • DFS
      • 位运算
    • 有重
      • DFS
  • 排列型枚举：排列
    • 无重
      • DFS(字典序)
    • 有重
      • DFS(字典序)
  • 组合型枚举：组合
    • 无重
      • DFS
      • 递推
      • 二进制字典序

$1 多项式型枚举：欧式空间的坐标

  • 枚举方式：for 循环
  • 状态空间规模：$n^{k}$
1
2
3
for(int i = 0; i < n; ++i)
    for(int j = 0; j < m; ++j)
        ...

$2 指数型枚举：子集

  • 枚举方式：递归，位运算
  • 状态空间规模：$k^{n}$

无重复集合：78. 子集

实现1: DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > result;
        vector<int> list;
        dfs(nums, 0, list, result);
        return result;
    }

private:
    void dfs(vector<int> &nums, int pos, vector<int> &list, vector<vector<int> > &result)
    {
        int n = nums.size();
        if(pos == n)
        {
            result.push_back(list);
            return;
        }
        list.push_back(nums[pos]);
        dfs(nums, pos + 1, list, result);
        list.pop_back();
        dfs(nums, pos + 1, list, result);
    }
};

实现2: 位运算

从 0 开始增加，到 1 << n 为止。

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
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > results;
        int n = nums.size();

        vector<int> result_item;
        unsigned int map = 0;
        unsigned int end = 1 << n; // 停止边界

        while(map < end)
        {
            for(int i = 0; i < n; ++i)
            {
                if((1 << i) & map)
                    result_item.push_back(nums[i]);
            }
            results.push_back(result_item);
            // 只清空元素，不释放内存
            // vector<int>().swap(MyObject)可以清空元素，释放内存。
            result_item.clear();
            ++map;
        }
        return results;
    }
};

有重复集合：90. 子集 II

实现: DFS

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
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int> > result;
        if(nums.empty()) return  result;
        sort(nums.begin(), nums.end());
        vector<int> list;
        vector<int> visited(nums.size(), false);
        dfs(nums, 0, list, result, visited);
        return result;
    }

private:
    void dfs(vector<int> &nums, int pos, vector<int> &list,
            vector<vector<int> > &result, vector<int> &visited)
    {
        int n = nums.size();
        if(pos == n)
        {
            result.push_back(list);
            return;
        }
        if(pos > 0 && nums[pos] == nums[pos - 1] && !visited[pos - 1])
        {
            visited[pos] = false;
            dfs(nums, pos + 1, list, result, visited);
        }
        else
        {
            list.push_back(nums[pos]);
            visited[pos] = true;
            dfs(nums, pos + 1, list, result, visited);
            list.pop_back();
            visited[pos] = false;
            dfs(nums, pos + 1, list, result, visited);
        }
    }
};

$3 排列型枚举：排列

  • 枚举方式：递归，迭代器(next_permutation)
  • 状态空间规模：$n!$

无重复排列：46. 全排列

实现: DFS(字典序输出)

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
class Solution {
public:
    vector<vector<int> > permute(vector<int>& nums) {
        vector<vector<int> > result;
        if(nums.empty()) return result;
        vector<int> cur_path;
        int n = nums.size();
        vector<bool> visited(n, false);
        dfs(nums, 0, cur_path, result, visited);
        return result;
    }

private:
    void dfs(vector<int> &nums, int pos, vector<int> &cur_path,
            vector<vector<int> > &result, vector<bool> &visited)
    {
        // pos 是当前考虑的路径的位置
        int n = nums.size();
        if(pos == n)
        {
            result.push_back(cur_path);
            return;
        }
        for(int i = 0; i < n; ++i)
        {
            if(visited[i]) continue;
            cur_path.push_back(nums[i]);
            visited[i] = true;
            dfs(nums, pos + 1, cur_path, result, visited);
            cur_path.pop_back();
            visited[i] = false;
        }
        return;
    }
};

有重复排列：47. 全排列 II

实现: DFS(字典序输出)

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
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int> > result;
        if(nums.empty()) return result;
        vector<int> cur_path;
        int n = nums.size();
        vector<bool> visited(n, false);
        sort(nums.begin(), nums.end());
        dfs(nums, 0, cur_path, result, visited);
        return result;
    }

private:
    void dfs(vector<int> &nums, int pos, vector<int> &cur_path,
            vector<vector<int> > &result, vector<bool> &visited)
    {
        // pos 是当前考虑的路径的位置
        int n = nums.size();
        if(pos == n)
        {
            result.push_back(cur_path);
            return;
        }
        for(int i = 0; i < n; ++i)
        {
            if(visited[i]) continue;
            if(i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]) continue;
            cur_path.push_back(nums[i]);
            visited[i] = true;
            dfs(nums, pos + 1, cur_path, result, visited);
            cur_path.pop_back();
            visited[i] = false;
        }
        return;
    }
};

$4 组合型枚举：组合

  • 枚举方式：递归(+剪枝)
  • 状态空间规模：$\dbinom{n}{m}$

无重复组合：77. 组合

实现1: DFS(字典序输出)

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
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        if(n < 1) return vector<vector<int> >();
        if(k > n) return vector<vector<int> >();
        // n >= 1, k <= n
        int pos = 1;
        vector<vector<int> > results;
        vector<int> result_item;
        dfs(results, result_item, pos, n, k);
        return results;
    }

private:
    void dfs(vector<vector<int> >& results, vector<int>& result_item, int pos, int n, int k)
    {
        int cur_len = result_item.size();
        if(cur_len == k)
        {
            results.push_back(result_item);
            return;
        }
        if(n - pos + 1 + cur_len < k) return; // 剪枝
        if(pos > n) return;

        result_item.push_back(pos);
        dfs(results, result_item, pos + 1, n, k);
        result_item.pop_back();
        dfs(results, result_item, pos + 1, n, k);
    }
};

实现2: DP，利用组合的递推式

1
C(n, k) = C(n - 1, k - 1) + C(n - 1, k - 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
28
29
30
31
32
class Solution_2 {
public:
    vector<vector<int>> combine(int n, int k) {
        if(n < 1) return vector<vector<int> >();
        if(k > n) return vector<vector<int> >();
        // k == 1 和 n == k 是递归的关键
        if(k == 1)
        {
            vector<vector<int> > results;
            for(int i = 1; i <= n; ++i)
                results.push_back(vector<int>({i}));
            return results;
        }
        if (n == k)
        {
            vector<int> row;
            for (int i = 1; i <= n; ++i)
                row.push_back(i); // select all
            vector<vector<int> > results;
            results.push_back(row);
            return results;
        }

        vector<vector<int> > results = combine(n - 1, k - 1);
        for(vector<int>& result_item: results)
            result_item.push_back(n);

        vector<vector<int> > results2 = combine(n - 1, k);
        results.insert(results.end(), results2.begin(), results2.end());
        return results;
    }
};

实现3: 二进制字典序

大致过程如下面的例子：

1
2
3
4
5
6
7
e.g. 1, 2, 3, 4  C(4, 2)
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0

二进制字典序是性能最优的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution_3 {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> nums(k, 0);
        for(int i = 1; i <= k; ++i)
            nums[i - 1] = i;
        nums.push_back(n + 1); // 哨兵

        vector<vector<int> > results;
        int j = 0;
        while(j < k)
        {
            results.push_back(vector<int>(nums.begin(), nums.begin() + k));
            j = 0;
            while(j < k && nums[j + 1] == nums[j] + 1)
            {
                nums[j] = j + 1; // 关键一行
                ++j;
            }
            ++nums[j];
        }
        return results;
    }
};
Share