算法搜索

常见的枚举方式

字数统计: 2.5k字   |   阅读时长: 11分
, , , ,

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

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

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

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

多项式型枚举、指数型枚举、排列型枚举都可以用回溯法实现，其状态空间树分别是 k 层满 n 叉树、子集树、排列树，在 回溯法三种常见的状态空间树：子集树、排列树、满m叉树 中，我们给出了用回溯法在这些状态空间树上搜索的更抽象的代码模板，可以与本文的代码模板对应看。

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

  • 枚举方式：回溯、for 循环
  • 状态空间规模：$n^{k}$，k 维欧式空间坐标，共 k 个分量，每个分类的取值为 1 ~ n。

for 循环方式枚举的代码模板如下：

1
2
3
4
for(int i = 0; i < n; ++i)
    for(int j = 0; j < n; ++j)
        for(int k = 0; k < n; ++k)
            ...

如果用回溯法，状态空间树为 k 层的满 n 叉树，代码大致如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Backtrack(int t)
{
    if(t > k)
        output(x);
    else
    {
        for(int i = 1; i <= n; i++)
        {
            if(constraint(t) && bound(t))
            {
                 x[t] = i;
                 // 做其他相关标识;
                 Backtrack(t + 1);
                 // 做其他相关标识的反操作; // 退回相关标识
            }
        }
    }
}

$2 指数型枚举：子集

  • 枚举方式：回溯，位运算
  • 状态空间规模：$2^{n}$，$n$ 个元素，每个有选和不选两种可能。

无重复元素集合的子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

提示：

1
2
3
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：
输入：nums = [0]
输出：[[],[0]]

实现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
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int> > result;
        vector<int> cur_path;
        dfs(nums, 0, cur_path, result);
        return result;
    }

private:
    void dfs(const vector<int> &nums, int pos, vector<int> &cur_path, vector<vector<int> > &result)
    {
        // pos 是子集树的深度
        // cur_path 是当前的搜索路径中选了的元素
        int n = nums.size();
        if(pos == n)
        {
            result.push_back(cur_path);
            return;
        }
        // 选 nums[pos]
        cur_path.push_back(nums[pos]);
        dfs(nums, pos + 1, cur_path, result);
        cur_path.pop_back();
        // 不选 nums[pos]
        dfs(nums, pos + 1, cur_path, 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;
    }
};

有重复元素集合的子集

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

提示：

1
2
1 <= nums.length <= 10
-10 <= nums[i] <= 10

示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：
输入：nums = [0]
输出：[[],[0]]

实现: 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>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int> > result;
        sort(nums.begin(), nums.end());
        vector<int> cur_path;
        dfs(nums, 0, cur_path, result, false);
        return result;
    }

private:
    void dfs(vector<int> &nums, int pos, vector<int> &cur_path,
            vector<vector<int> > &result, bool prev_visit)
    {
        // pos 是子集树的深度
        // cur_path 是当前的搜索路径中选了的元素
        int n = nums.size();
        if(pos == n)
        {
            result.push_back(cur_path);
            return;
        }
        if(pos > 0 && nums[pos] == nums[pos - 1] && !prev_visit)
        {
            // 剪枝函数，如果 nums[pos] = nums[pos - 1]，且 nums[pos - 1] 没选 (!prev_visit)
            // 则剪掉选 nums[pos] 的这一支
            dfs(nums, pos + 1, cur_path, result, false);
        }
        else
        {
            cur_path.push_back(nums[pos]);
            dfs(nums, pos + 1, cur_path, result, true);
            cur_path.pop_back();
            dfs(nums, pos + 1, cur_path, result, false);
        }
    }
};

无重复元素集合的子集，子集有k个元素

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

提示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
1 <= n <= 20
1 <= k <= n

>示例 1：
>输入：n = 4, k = 2
>输出：
>[
>  [2,4],
>  [3,4],
>  [2,3],
>  [1,2],
>  [1,3],
>  [1,4],
>]
>
>示例 2：
>输入：n = 1, k = 1
>输出：[[1]]

实现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
32
33
34
35
36
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> cur_path; // 结果列表
        dfs(pos, cur_path, results, n, k);
        return results;
    }

private:
    void dfs(int pos, vector<int>& cur_path, vector<vector<int> >& results, const int n, const int k)
    {
        // cur_path 是当前的搜索路径中选了的元素
        int cur_len = cur_path.size();
        if(cur_len == k)
        {
            // 可行解的判断函数
            results.push_back(cur_path);
            return;
        }
        if(pos > n)
            return;
        // pos 是当前考察到的数字，也是子集树的深度
        if(n - pos + 1 + cur_len < k) 
            return; // 剪枝：后续的 n - pos + 1 即使全选也无法达到 k 个

        cur_path.push_back(pos);
        dfs(pos + 1, cur_path, results, n, k);
        cur_path.pop_back();
        dfs(pos + 1, cur_path, results, 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 {
public:
    vector<vector<int>> combine(int n, int k) {
        if(n < 1 || 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 排列型枚举：排列

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

无重复元素集合的排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

提示：

1
2
3
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：
输入：nums = [1]
输出：[[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
class Solution {
public:
    vector<vector<int> > permute(vector<int>& nums) {
        vector<vector<int> > result;
        vector<int> cur_path = nums;
        dfs(0, cur_path, result);
        return result;
    }

private:
    void dfs(int pos, vector<int> &cur_path, vector<vector<int> > &result)
    {
        // pos 是当前考虑的路径的位置，排列树的深度
        // cur_path[0..pos-1] 是当前的搜索路径
        int n = cur_path.size();
        if(pos == n)
        {
            result.push_back(cur_path);
            return;
        }
        for(int i = pos; i < n; ++i)
        {
            swap(cur_path[pos], cur_path[i]);
            dfs(pos + 1, cur_path, result);
            swap(cur_path[pos], cur_path[i]);
        }
    }
};

有重复元素集合的排列

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

提示：

1
2
1 <= nums.length <= 8
-10 <= nums[i] <= 10

示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,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
32
33
34
class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int> > result;
        vector<int> cur_path = nums;
        dfs(0, cur_path, result);
        return result;
    }

private:
    void dfs(int pos, vector<int> &cur_path, vector<vector<int> > &result)
    {
        // pos 是当前考虑的路径的位置，排列树的深度
        // cur_path[0..pos-1] 是当前的搜索路径
        int n = cur_path.size();
        if(pos == n)
        {
            result.push_back(cur_path);
            return;
        }
        unordered_set<int> setting;
        for(int i = pos; i < n; ++i)
        {
            // 剪枝函数，如果 nums[pos] 此前选过 cur_path[i] 的值了，则 pos 位置不选 cur_path[i]
            // 剪掉 cur_path[pos] 选 cur_path[i] 的这一支
            if(setting.count(cur_path[i]) > 0) 
                continue;
            setting.insert(cur_path[i]);
            swap(cur_path[pos], cur_path[i]);
            dfs(pos + 1, cur_path, result);
            swap(cur_path[pos], cur_path[i]);
        }
    }
};
Share