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

news/2025/3/28 8:04:48/

一、排列问题（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/news/1583001.html

相关文章

0基础学前端----移动WEB开发之flex布局DAY15

0基础学前端----移动WEB开发之flex布局DAY15

0基础学前端—移动WEB开发之flex布局DAY15 视频参考&#xff1a;B站Pink老师 本节重点&#xff1a;flex盒子布局原理、flex布局常用属性、携程移动端首页案例 本章目录 0基础学前端---移动WEB开发之flex布局DAY15目标1. flex布局体验1.1 传统布局和flex布局 2. flex布局原理2…
阅读更多...
leetcode每日一题：酿造药水需要的最少总时间

leetcode每日一题：酿造药水需要的最少总时间

引言 今天的每日一题原题是2255. 统计是给定字符串前缀的字符串数目&#xff0c;直接模拟&#xff0c;逐个匹配words中的字符串是否是s的前缀即可。更换成前几天遇到的更有意思的一题来写这个每日一题。 题目 给你两个长度分别为 n 和 m 的整数数组 skill 和 mana 。 在一个…
阅读更多...
分布式算法：Paxos Raft 两种共识算法

分布式算法：Paxos Raft 两种共识算法

1. Paxos算法 Paxos算法是 Leslie Lamport&#xff08;莱斯利兰伯特&#xff09;在 1990 年提出的一种分布式系统共识算法。也是第一个被证明完备的共识算法&#xff08;前提是不存在恶意节点&#xff09;。 1.1 简介 Paxos算法是第一个被证明完备的分布式系统共识算法。共识…
阅读更多...
Android第六次面试总结（Java设计模式二）

Android第六次面试总结（Java设计模式二）

在 Android 开发里&#xff0c;ListView 和 RecyclerView 是常用的视图组件&#xff0c;用于展示大量数据列表。不过&#xff0c;这些视图组件本身无法直接展示原始数据源&#xff0c;需要借助 Adapter&#xff08;适配器&#xff09;把数据源适配成视图能够展示的数据&#xf…
阅读更多...
空调遥控器低功耗单片机方案

空调遥控器低功耗单片机方案

RAMSUN空调遥控器采用先进的32位低功耗单片机作为核心控制器&#xff0c;通过优化软件算法和硬件设计&#xff0c;实现了空调遥控器的低功耗运行。单片机集成了多种功能模块&#xff0c;包括红外发射、按键扫描、电源管理等&#xff0c;有效降低了整体功耗。同时&#xff0c;该…
阅读更多...
C++20新特性：std::assume_aligned详解

C++20新特性：std::assume_aligned详解

文章目录 一、概述二、函数定义与语法三、使用方法与注意事项1. 使用方法2. 注意事项 四、性能优化原理五、实际应用场景六、编译器支持情况七、总结 一、概述 C20引入了std::assume_aligned&#xff0c;这是一个非常实用的特性&#xff0c;用于告知编译器某个指针所指向的对象…
阅读更多...
ElasticSearch快速入门--实现分词搜索

ElasticSearch快速入门--实现分词搜索

分词题目搜索 使用Elasticsearch实现题目数据的存储和分词搜索&#xff0c;需要将数据库的数据同步到 Elasticsearch。 ElasticSearch入门 ElasticSearch&#xff08;简称ES&#xff09;是一个开源的分布式搜索和数据分析引擎&#xff0c;用Java开发并且是当前最流行的开源的…
阅读更多...
uniapp 微信小程序图片下载保存功能

uniapp 微信小程序图片下载保存功能

在开发这个功能之前&#xff0c;要先确保小程序的隐私条约是否加上相册&#xff08;仅写入&#xff09;权限&#xff0c;设置路径&#xff1a;微信公众平台->账号设置&#xff08;左下角头像悬停&#xff09;->用户隐私保护指引&#xff08;去完善&#xff09;->相册&…
阅读更多...
最新文章

Copyright @ 2022~2023