首页 > 编程札记 > 编程

C++全排列带你初步理解DFS回溯

阅读：评论：0

C++全排列带你初步理解DFS回溯

文章目录

前言
全排列1
- 思路
全排列2
- 思路
结尾
- LeetCode原题链接

前言

相信有一些小伙伴也被DFS(深度优先搜索） 或者 回溯算法所困扰过，包括我也是，不过最近经朋友推荐了LeetCode46，47两题，做完了之后，简直入醍醐灌顶，瞬间通透了。话不多说，直接给大家上题。

全排列1

给定一个不含重复数字的数组 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]]

提示：

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

思路

1、首先题目需要返回的是所有的路径结果，所以第一眼想到就是DFS和回溯
2、每一次搜索都回溯一下，为了防止重复使用到某一元素，我引入了一个bool 数组，在每一个排列中，只要该数字被使用了，就标记为 true
3、遇到被使用的数字，就直接跳过

#include<iostream>
#include<vector>
using namespace std;/*
dfs,回溯，每一次通过一个bool数组，记录此次排列中某一数字是否被使用
*/void dfs(vector<vector<int>>& res, vector<int>& nums,vector<bool>& flag,vector<int> &path){if(path.size()==nums.size()){   //出口，排列长度==原数组长度res.push_back(path);return;}for(int i=0;i<nums.size();i++){if(flag[i]==true)   continue;   //如果该数字被使用，就直接下一个flag[i]=true;	//标记使用path.push_back(nums[i]);dfs(res,nums,flag,path);path.pop_back();flag[i]=false;	//回溯，解除标记}
}   vector<vector<int>> permute(vector<int>& nums) {vector<vector<int>> res;vector<bool> flag(nums.size());     //标记数组，默认赋值是falsevector<int> path;	//存放一次排列dfs(res,nums,flag,path);return res;
}int main(){vector<vector<int>> res;vector<int> nums={1,2,3};res=permute(nums);for(auto i:res){for(auto j:i){cout<<j<<" ";}cout<<endl;}return 0;
}

全排列2

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

示例 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]]

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10
通过次数285,408提交次数443,090

思路

这题基本上和上题一样，但是加入了重复的数字。题目是要不能输出重复的全排列。什么意思呢？
举个例子：假如有 2 2 两个数字，假设第一个2 为 2a ，第二个 2 为 2b ，他们出现的顺序就可能为 2a2b 和 2b2a 两种，但是这两种其实都是一样的，题目就是只能输出其中的一种，不能两个都同时存在，同时存在的话，就是重复的全排列了。
为了使最终的结果不出现重复的情况，我们便先对原数组进行排序，使相同的元素都在一起
然后设置条件，让重复的元素，只能以一种顺序输出，即 2a2b这种，按顺序的输出。其他任何情况都不允许。
剩下的便和上题基本一样了，同样引入标记数组，标记已经使用了的数字

#include<iostream>
#include<vector>
using namespace std;
#include<algorithm>/*
*不能出现重复的排列
例如：相同的数字  3 3  ，假设第一个3 为 3a ,第二个为 3b ,他们之间的排列就有  3a 3b  ,  3b 3a 两种
为了限制只能出现一种，我们便可以让她固定只能 以一种顺序出现，即 3a3b ，其他的任何顺序都是不允许的我们先对原始数组进行排列，让相同的数字都在一起，然后运用回溯，使用一个标记数组，标记每一个排列中，已经被使用的数字
*/void dfs(vector<vector<int>>& res,vector<int>& nums,vector<bool>& flag,vector<int>& path){if(path.size()==nums.size()){res.push_back(path);return ;}for(int i=0;i<nums.size();i++){//1、已经使用了的跳过//2、相同的数字，不符合我们设定的顺序，也直接跳过if(flag[i] ||i>0 && nums[i]==nums[i-1] && flag[i-1]==false){continue;}flag[i]=true;path.push_back(nums[i]);dfs(res,nums,flag,path);path.pop_back();flag[i]=false;}
}vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),d());	//对原数组进行排序，使相同的元素相邻vector<vector<int>> res;vector<bool> flag(nums.size()); //默认赋值为falsevector<int> path;   //记录每一组排列dfs(res,nums,flag,path);return res;}int main(){vector<vector<int>> res;vector<int> nums={3,0,3,3};res=permuteUnique(nums);for(auto i:res){for(auto j:i){cout<<j<<" ";}cout<<endl;}return 0;
}