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

前言全排列1

思路 全排列2

思路 结尾

LeetCode原题链接

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

给定一个不含重复数字的数组 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
#include
using namespace std;



void dfs(vector>& res, vector& nums,vector& flag,vector &path){
    if(path.size()==nums.size()){   //出口，排列长度==原数组长度
        res.push_back(path);
        return;
    }

    for(int i=0;i> permute(vector& nums) {
    vector> res;
    vector flag(nums.size());     //标记数组，默认赋值是false
    vector path;	//存放一次排列
    dfs(res,nums,flag,path);
    return res;
}

int main(){
    vector> res;
    vector nums={1,2,3};
    res=permute(nums);

    for(auto i:res){
        for(auto j:i){
            cout< 
全排列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
#include
using namespace std;
#include



void dfs(vector>& res,vector& nums,vector& flag,vector& path){
    if(path.size()==nums.size()){
        res.push_back(path);
        return ;
    }

    for(int i=0;i0 && 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> permuteUnique(vector& nums) {
    sort(nums.begin(),nums.end());	//对原数组进行排序，使相同的元素相邻
    vector> res;
    vector flag(nums.size()); //默认赋值为false
    vector path;   //记录每一组排列
    dfs(res,nums,flag,path);
    return res;

}

int main(){
    vector> res;
    vector nums={3,0,3,3};
    res=permuteUnique(nums);

    for(auto i:res){
        for(auto j:i){
            cout< 
结尾 
吃透对两个题目，对大家理解DFS和回溯还是很有用的，我就是通过这个题目才真正的理解一些DFS和回溯。希望本篇文章能够帮助到你。
 我讲的可能不是细致。大家可以点击下面链接，去LeetCode官方原题下，看其他大神的讲解。
 
LeetCode原题链接 
LeetCode 46. 全排列
 LeetCode 47.全排列Ⅱ