题目描述

输入一组数字（可能包含重复数字），输出其所有的排列方式。

解题思路(1)(最容易想到的)

法1:创建一个二维的vector(目的是引入数据的同时将输入流对应的结果保存再一起)
先sort排序然后直接使用algorithm头文件里面的算法
    注意:要使用do_while循环,否则一个元素输入的情况会被吃掉
每次while循环都会用算法产生一个新的序列,然后被储存再vector s里面,最后返回输出s即可

C++ 代码(1)

class Solution {
public:
    vector<vector<int>> permutation(vector<int>& nums) {    
    sort(nums.begin(),nums.end());                      //首先从小到大排序,方便顺序排序
    vector<vector<int>>s;                               //定义一个二维的向量,用于存储所有结果
        do{
            s.push_back(nums);                          //将排序方式储存在s向量里面
        }
        while(next_permutation(nums.begin(),nums.end()));//while循环连续使用算法,直到没有新的排序了
    return s;                                           //返回储存答案的s向量
    }
};

解题思路(2)(学习dfs的写法)

法2:创建一个二维向量用于储存数据和输出结果,还要创建一个path存储当前的遍历路径和st标记当前位置的数字是否已被选取.然后对nums排序调用dfs得到结果.
注意:u是函数的参数,在调用dfs的时候从0开始递增到nums.size()

C++代码(2)

class Solution {
public:
    vector<vector<int>> res;    //用于存储所有的结果（所有可能的排列）
    vector<int> path;           //用于存储当前的遍历路径（即当前排列）
    vector<int> st;             //用于标记当前位置的数字是否已被选取，避免重复选取

    vector<vector<int>> permutation(vector<int>& nums) {
        path.resize(nums.size());// 根据nums的大小调整path的大小
        st.resize(nums.size());  // 根据nums的大小调整st的大小
        sort(nums.begin(), nums.end());// 对nums进行排序，方便后续的dfs遍历
        dfs(nums, 0, 0);         // 调用dfs遍历(固定格式)这里就声明u是0了
        return res;              // 返回所有结果
    }

    void dfs(vector<int>& nums, int u, int start) {// 定义dfs，进行深搜
        if (u == nums.size()) {  // 如果已经处理完所有的元素（即u等于nums的长度)
            res.push_back(path); //则将当前的路径path加入到结果向量res中,程序结束
            return;
        }
        for (int i = start; i < nums.size(); i ++ ) {//从start开始遍历nums，对还未被选取的元素进行处理
            if (!st[i]) {       // 如果当前位置的数字还未被选取（st[i]为假）
                st[i] = true;   // 将当前位置的数字标记为已被选取（st[i]设为真）
                path[i] = nums[u];//将当前处理的nums中的值加入到当前的排列中
                if (u + 1 < nums.size() && nums[u] != nums[u + 1]){// 如果下一个元素与当前元素相同，则从下一个元素的下一个位置开始处理；
                    dfs(nums,u+1,0);
                }else{          //否则从开始位置重新处理。这里主要为了跳过重复的元素。
                    dfs(nums,u+1,i+1);
                }
                st[i] = false; //处理结束后，将当前位置的数字重新设为未选取状态
            }
        }
    }
};

篇章

上一篇:AcWing 75. 和为S的两个数字
https://www.acwing.com/solution/content/213215/
下一篇:AcWing 26. 二进制中1的个数
https://www.acwing.com/solution/content/213289/