深度优先搜索（DFS）在排列组合问题中的应用详解：C++实现与优化

devtools/2025/3/26 11:10:35/

一、排列问题（Permutations）

目标：生成所有可能的排列（元素顺序不同视为不同结果）。
示例：输入 [1,2,3]，输出所有长度为3的排列，共6种。

C++实现代码

#include <iostream>
#include <vector>
using namespace std;void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {if (path.size() == nums.size()) {res.push_back(path);  // 保存当前排列return;}for (int i = 0; i < nums.size(); ++i) {if (!used[i]) {  // 选择未使用的元素used[i] = true;path.push_back(nums[i]);backtrack(nums, used, path, res);  // 递归path.pop_back();  // 回溯used[i] = false;}}
}vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> res;vector<bool> used(nums.size(), false);vector<int> path;backtrack(nums, used, path, res);return res;
}int main() {vector<int> nums = {1, 2, 3};auto permutations = permute(nums);for (auto& p : permutations) {for (int num : p) {cout << num << " ";}cout << endl;}return 0;
}

输出：

1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1

关键点：

  • 去重：通过used数组标记已使用的元素，避免重复选择。

  • 回溯：递归后需撤销当前选择（path.pop_back()和used[i] = false），以尝试其他分支。

二、组合问题（Combinations）

目标：生成所有可能的组合（元素顺序不同视为相同结果）。
示例：从 [1,2,3] 中选2个元素，输出 {1,2}, {1,3}, {2,3}。

C++实现代码

#include <iostream>
#include <vector>
using namespace std;void backtrack(int start, int k, vector<int>& nums, vector<int>& path, vector<vector<int>>& res) {if (path.size() == k) {res.push_back(path);  // 保存当前组合return;}for (int i = start; i < nums.size(); ++i) {path.push_back(nums[i]);backtrack(i + 1, k, nums, path, res);  // 下一层从i+1开始，避免重复path.pop_back();  // 回溯}
}vector<vector<int>> combine(vector<int>& nums, int k) {vector<vector<int>> res;vector<int> path;backtrack(0, k, nums, path, res);return res;
}int main() {vector<int> nums = {1, 2, 3};int k = 2;auto combinations = combine(nums, k);for (auto& c : combinations) {for (int num : c) {cout << num << " ";}cout << endl;}return 0;
}

输出：

1 2 
1 3 
2 3

关键点：

  • 顺序控制：每次递归从i+1开始，避免选择之前的元素，保证组合无序性。

  • 剪枝优化：若剩余元素不足以填满组合，可提前终止循环。

三、处理重复元素

1. 含重复元素的排列去重

示例：输入 [1,1,2]，输出不重复的排列 [1,1,2], [1,2,1], [2,1,1]。

优化代码：

void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {if (path.size() == nums.size()) {res.push_back(path);return;}for (int i = 0; i < nums.size(); ++i) {if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) {continue;  // 跳过重复元素}used[i] = true;path.push_back(nums[i]);backtrack(nums, used, path, res);path.pop_back();used[i] = false;}
}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());  // 必须排序vector<vector<int>> res;vector<bool> used(nums.size(), false);vector<int> path;backtrack(nums, used, path, res);return res;
}

关键点：

  • 排序：预处理数组，使相同元素相邻。

  • 剪枝条件：nums[i] == nums[i-1] && !used[i-1] 表示跳过重复且未被使用的元素。

2. 含重复元素的组合去重

示例：输入 [1,2,2]，输出不重复的组合 [1,2], [2,2]。

优化代码：

void backtrack(int start, int k, vector<int>& nums, vector<int>& path, vector<vector<int>>& res) {if (path.size() == k) {res.push_back(path);return;}for (int i = start; i < nums.size(); ++i) {if (i > start && nums[i] == nums[i-1]) {continue;  // 跳过重复元素}path.push_back(nums[i]);backtrack(i + 1, k, nums, path, res);path.pop_back();}
}vector<vector<int>> combineUnique(vector<int>& nums, int k) {sort(nums.begin(), nums.end());  // 必须排序vector<vector<int>> res;vector<int> path;backtrack(0, k, nums, path, res);return res;
}

关键点：

  • 排序：预处理数组，使相同元素相邻。

  • 剪枝条件：i > start && nums[i] == nums[i-1] 跳过同一层中的重复元素。

四、时间复杂度分析

问题类型时间复杂度空间复杂度
排列（无重复）O(n×n!)O(n)
组合（无重复）O(C(n,k) ×k)O(k)
排列（有重复）O(n×n!/m!)（m为重复数）O(n)
组合（有重复）O(C(n,k) ×k)O(k)

五、应用场景

  • 排列：密码破解、任务调度、路径规划。

  • 组合：子集生成、商品搭配、团队选拔。

六、总结

  • DFS核心：通过递归和回溯遍历所有可能的分支。

  • 排列与组合区别：排列关注顺序，组合不关注顺序。

  • 去重关键：排序 + 剪枝条件（跳过重复元素）。

  • 优化技巧：剪枝提前终止无效分支，减少递归深度。

七、排列问题例题

1、输出全排列

P1706 全排列问题 - 洛谷

算法代码： 

#include<bits/stdc++.h>  // 包含常用的C++标准库头文件
using namespace std;    // 使用标准命名空间int n;                  // 定义一个全局变量n，表示排列的长度
int vis[10];            // 定义一个大小为10的数组vis，用于标记某个数字是否已经被使用过
int a[10];              // 定义一个大小为10的数组a，用于存储1到n的数字
int b[10];              // 定义一个大小为10的数组b，用于存储当前生成的排列// 定义一个递归函数dfs，用于生成所有可能的排列
void dfs(int step)
{// 如果step等于n+1，说明已经生成了一个完整的排列if(step==n+1){// 输出当前排列for(int i=1;i<=n;i++){printf("%5d",b[i]);  // 每个数字占5个字符宽度}printf("\n");  // 换行return;  // 返回上一层递归}// 遍历1到n的所有数字for(int i=1;i<=n;i++){// 如果数字i没有被使用过if(vis[i]==0){b[step]=a[i];  // 将数字i放入当前排列的第step个位置vis[i]=1;      // 标记数字i为已使用dfs(step+1);   // 递归调用dfs，生成下一个位置的数字vis[i]=0;      // 回溯，取消数字i的标记}}return;  // 返回上一层递归
}int main()
{cin>>n;  // 输入排列的长度n// 初始化数组a，a[i] = ifor(int i=1;i<=n;i++){a[i]=i;          }dfs(1);  // 从第1个位置开始生成排列return 0;  // 程序正常结束
}

图解流程： 

2、输出部分排列（需注意）

        上述的代码是实现打印n个数的全排列，若我需要打印从 n 个数中任意选取 m 个数的排列，需要做以下两处修改：

  1. 修改 dfs 函数的终止条件：

    • 原代码的终止条件是 step == n + 1，表示生成了完整的 n 个数的排列。

    • 现在需要改为 step == m + 1，表示生成了 m 个数的排列。

  2. 修改主函数中的输入和初始化：

    • 需要额外输入一个变量 m，表示从 n 个数中选取 m 个数进行排列。

#include<bits/stdc++.h>  // 包含常用的C++标准库头文件
using namespace std;    // 使用标准命名空间int n, m;              // 定义全局变量n和m，n表示总数，m表示选取的数的个数
int vis[10];            // 定义一个大小为10的数组vis，用于标记某个数字是否已经被使用过
int a[10];              // 定义一个大小为10的数组a，用于存储1到n的数字
int b[10];              // 定义一个大小为10的数组b，用于存储当前生成的排列// 定义一个递归函数dfs，用于生成从n个数中选取m个数的排列
void dfs(int step)
{// 如果step等于m+1，说明已经生成了一个完整的m个数的排列if(step == m + 1){// 输出当前排列for(int i = 1; i <= m; i++){printf("%5d", b[i]);  // 每个数字占5个字符宽度}printf("\n");  // 换行return;  // 返回上一层递归}// 遍历1到n的所有数字for(int i = 1; i <= n; i++){// 如果数字i没有被使用过if(vis[i] == 0){b[step] = a[i];  // 将数字i放入当前排列的第step个位置vis[i] = 1;      // 标记数字i为已使用dfs(step + 1);  // 递归调用dfs，生成下一个位置的数字vis[i] = 0;     // 回溯，取消数字i的标记}}return;  // 返回上一层递归
}int main()
{cin >> n >> m;  // 输入总数n和选取的数的个数m// 初始化数组a，a[i] = ifor(int i = 1; i <= n; i++){a[i] = i;          }dfs(1);  // 从第1个位置开始生成排列return 0;  // 程序正常结束
}

示例运行：

假设输入：

n = 4
m = 2

输出将是：

    1    21    31    42    12    32    43    13    23    44    14    24    3 

3、输出组合（打印n个数中m个数的组合）（重要）

在DFS中，选择或者不选择第k个数就实现了各种组合。以下举两个例子：

（1）输出二进制

以打印000~111为例：

#include<bits/stdc++.h>  // 包含常用的C++标准库头文件
using namespace std;    // 使用标准命名空间int vis[10];            // 定义一个大小为10的数组vis，用于存储当前的状态（0或1）// 定义一个递归函数dfs，用于生成所有可能的二进制组合
void dfs(int k)
{// 如果k等于4，说明已经生成了一个完整的3位二进制组合if(k == 4){// 输出当前生成的3位二进制组合for(int i = 1; i < 4; i++){cout << vis[i];  // 输出vis数组的第1到第3个元素}cout << " ";  // 换行}else{vis[k] = 0;    // 将当前位设置为0dfs(k + 1);    // 递归调用dfs，生成下一位vis[k] = 1;    // 将当前位设置为1dfs(k + 1);    // 递归调用dfs，生成下一位}
}int main()
{dfs(1);  // 从第1位开始生成二进制组合return 0;  // 程序正常结束
}

代码功能：

这段代码的功能是生成所有可能的3位二进制组合（从 000 到 111），并输出这些组合。

代码流程：

  1. 初始化：

    • 定义了一个全局数组 vis，用于存储每一位的状态（0或1）。

    • 数组大小为10，但实际只用到前3位（索引1到3）。

  2. 递归函数 dfs：

    • 参数 k 表示当前正在处理的位数。

    • 如果 k == 4，说明已经生成了一个完整的3位二进制组合，输出 vis[1] 到 vis[3] 的值。

    • 否则：

      • 将当前位 vis[k] 设置为0，然后递归调用 dfs(k + 1)，生成下一位。

      • 将当前位 vis[k] 设置为1，然后递归调用 dfs(k + 1)，生成下一位。

  3. 主函数 main：

    • 调用 dfs(1)，从第1位开始生成二进制组合。

输出结果：

运行代码后，输出将是所有3位二进制组合：

000 001 010 011 100 101 110 111

如果要反过来，只需交换选择数字0或1的逻辑选择代码行就可以了，输出：111 110 101 100 011 010 001 000，即：

#include<bits/stdc++.h>  // 包含常用的C++标准库头文件
using namespace std;    // 使用标准命名空间int vis[10];            // 定义一个大小为10的数组vis，用于存储当前的状态（0或1）// 定义一个递归函数dfs，用于生成所有可能的二进制组合
void dfs(int k)
{// 如果k等于4，说明已经生成了一个完整的3位二进制组合if(k == 4){// 输出当前生成的3位二进制组合for(int i = 1; i < 4; i++){cout << vis[i];  // 输出vis数组的第1到第3个元素}cout << " ";  // 换行}else{vis[k] = 1;    // 将当前位设置为0dfs(k + 1);    // 递归调用dfs，生成下一位vis[k] = 0;    // 将当前位设置为1dfs(k + 1);    // 递归调用dfs，生成下一位}
}int main()
{dfs(1);  // 从第1位开始生成二进制组合return 0;  // 程序正常结束
}

（2）输出组合

以包含3个元素的集合{a,b,c}为例子，输出它的所有的子集。

#include<bits/stdc++.h>  // 包含常用的C++标准库头文件，如iostream、vector、algorithm等
using namespace std;    // 使用标准命名空间，避免每次调用标准库函数时都要加std::char a[] = {' ', 'a', 'b', 'c'};  // 定义字符数组a，包含空格和字母a、b、c，用于生成组合时选择字符
int vis[10];  // 定义状态数组vis，用于存储当前的状态（0或1），表示是否选择对应位置的字符// 定义一个递归函数dfs，用于生成所有可能的组合
void dfs(int k)
{// 如果k等于4，说明已经生成了一个完整的3位组合if(k == 4){// 输出当前生成的3位组合for(int i = 1; i < 4; i++){if(vis[i])cout << a[i];  // 如果vis[i]为1，输出字符数组a中对应的字符}cout << " ";  // 输出空格分隔不同的组合}else{vis[k] = 0;  // 将当前位设置为0，表示不选择字符数组a中的对应字符（即选择空格）dfs(k + 1);  // 递归调用dfs，生成下一位的组合vis[k] = 1;  // 将当前位设置为1，表示选择字符数组a中的对应字符dfs(k + 1);  // 递归调用dfs，生成下一位的组合}
}int main()
{dfs(1);  // 从第1位开始生成组合return 0;  // 程序正常结束
}

代码功能解释：

  • 该代码通过递归函数 dfs 生成所有可能的3位组合，组合中的每一位可以是空格或字符 a、b、c。

  • vis 数组用于记录每一位是否选择字符（1表示选择，0表示不选择）。

  • 当 k == 4 时，表示已经生成了一个完整的3位组合，此时遍历 vis 数组，输出对应的字符。

  • 递归过程中，每次调用 dfs 时，都会尝试将当前位设置为0或1，然后继续递归生成下一位的组合。

输出示例：

运行该代码会输出所有可能的3位组合，例如：

   a b c ab ac bc abc

（其中空格表示未选择字符）


http://www.ppmy.cn/devtools/171331.html

相关文章

【网络】HTTP 和 HTTPS

【网络】HTTP 和 HTTPS

HTTP&#xff08;HyperText Transfer Protocol&#xff09;和 HTTPS&#xff08;HTTP Secure&#xff09;是互联网数据通信的核心协议&#xff0c;作为前端开发者&#xff0c;深入理解其原理和细节对性能优化、安全加固和问题排查至关重要。 一.HTTP核心概念 1.请求方法 GET…
阅读更多...
力扣13. 罗马数字转整数：Java多种解法详解

力扣13. 罗马数字转整数：Java多种解法详解

力扣13. 罗马数字转整数&#xff1a;Java多种解法详解 题目描述 罗马数字由以下字符构成&#xff1a;I, V, X, L, C, D, M&#xff0c;分别对应数值1, 5, 10, 50, 100, 500, 1000。 特殊规则&#xff1a;当小值字符位于大值字符左侧时&#xff0c;表示减法&#xff08;如 IV4…
阅读更多...
linux0.11内核源码修仙传第九章——时间初始化

linux0.11内核源码修仙传第九章——时间初始化

&#x1f680; 前言 本文主要解释了计算机断电重启后能准确读取时间的原因&#xff0c;内容很短&#xff0c;对应于书中的第17回。希望各位给个三连&#xff0c;拜托啦&#xff0c;这对我真的很重要&#xff01;&#xff01;&#xff01; 目录 &#x1f680; 前言&#x1f3c6;…
阅读更多...
【微服务架构】本地负载均衡的实现（基于随机算法）

【微服务架构】本地负载均衡的实现（基于随机算法）

前言 负载均衡 概念&#xff1a;一种将网络流量或业务请求均匀分配到多个服务器或服务实例上的技术&#xff0c;旨在提高系统的可用性、性能和可伸缩性。作用&#xff1a; 提高性能&#xff1a;通过将请求分散到多个实例上&#xff0c;避免单个实例因请求过多而过载&#xff…
阅读更多...
GMII 接口

GMII 接口

文章目录 概述硬件拓扑GMII 接口站管理接口发送数据时序接收数据时序参考 本文为笔者学习以太网对网上资料归纳整理所做的笔记&#xff0c;文末均附有参考链接&#xff0c;如侵权&#xff0c;请联系删除。 概述 GMII 是千兆网的MII接口&#xff0c;这个也有相应的 RGMII 接口&…
阅读更多...
笔试专题（三）

笔试专题（三）

文章目录 字符串中找出连续最长的数字串题解代码 拼三角题解代码 字符串中找出连续最长的数字串 题目链接 题解 1. 考察双指针 模拟 2. 算法思路&#xff1a;给定一个i 0&#xff0c;让i&#xff0c;如果遇到数字字符就创建一个变量j i&#xff0c;让j去遍历&#xff0c…
阅读更多...
Rust从入门到精通之进阶篇：20.项目实践

Rust从入门到精通之进阶篇：20.项目实践

项目实践 在本章中，我们将把前面学到的所有 Rust 知识整合起来，构建一个完整的应用程序。通过实际项目，你将学习如何组织代码、处理依赖关系、实现功能以及测试和部署 Rust 应用程序。我们将构建一个命令行待办事项管理器（Todo CLI），它具有添加、列出、完成和删除任务的…
阅读更多...
深入理解指针（2）（C语言版）

深入理解指针（2）（C语言版）

文章目录 前言一、数组名的理解二、使用指针访问数组三、一维数组传参的本质四、冒泡排序五、二级指针六、指针数组七、指针数组模拟二维数组总结 前言 在上一篇文章中&#xff0c;我们初步了解了指针的基本概念和用法。今天&#xff0c;我们将继续深入探索指针在数组、函数传…
阅读更多...
最新文章

Copyright @ 2022~2023