数字排列_ 字节宝

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

样例

代码语言：txt复制

输入：[1,2,3]

代码语言：txt复制

输出：

代码语言：txt复制

        [1,2,3],

代码语言：txt复制

        [1,3,2],

代码语言：txt复制

        [2,1,3],

代码语言：txt复制

        [2,3,1],

代码语言：txt复制

        [3,1,2],

代码语言：txt复制

        [3,2,1]

代码语言：txt复制

分析：

回溯的经典题

回溯的思路：

先找一个路径出来，记录下来这个路径。
擦掉最后一次的查找记录，返回上一层
重新找倒数第二层，找到以后继续找下一层，直到找到一个新的路径
限定条件：每一层查找出来的数字都必须和其他不同

时间复杂度分析：

个内部节点，在每个内部节点内均会for循环 n

代码语言：txt复制

class Solution {

代码语言：txt复制

public:

代码语言：txt复制

    vector<vector<int>> res;//结果数组

代码语言：txt复制

    vector<bool> st;//状态数组

代码语言：txt复制

    vector<int> path;//保存当前路径的数

代码语言：txt复制

    vector<vector<int>> permutation(vector<int>& nums) {

代码语言：txt复制

        for(int i=0; i<nums.size(); i  ) st.push_back(false);

代码语言：txt复制

        dfs(nums, 0);

代码语言：txt复制

        return res;

代码语言：txt复制

    void dfs(vector<int>& nums, int u) {

代码语言：txt复制

        if (u == nums.size()) {//u==nums.size()说明当前路径结束，返回一种情况

代码语言：txt复制

            res.push_back(path);

代码语言：txt复制

            return;

代码语言：txt复制

        for(int i=0; i<nums.size(); i  ) {

代码语言：txt复制

            if(!st[i]) {

代码语言：txt复制

                st[i] = true;

代码语言：txt复制

                path.push_back(nums[i]);

代码语言：txt复制

                dfs(nums, u 1);

代码语言：txt复制

                //从每个分支退回来的时候需要把修改过的状态还原

代码语言：txt复制

                st[i] = false;

代码语言：txt复制

                path.pop_back();

代码语言：txt复制

};

再看一题可能包含重复数字的

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

样例

代码语言：txt复制

输入：[1,2,3]

代码语言：txt复制

输出：

代码语言：txt复制

        [1,2,3],

代码语言：txt复制

        [1,3,2],

代码语言：txt复制

        [2,1,3],

代码语言：txt复制

        [2,3,1],

代码语言：txt复制

        [3,1,2],

代码语言：txt复制

        [3,2,1]

代码语言：txt复制

分析：

由于有重复元素的存在，这道题的枚举顺序和上次不同。

先将所有数从小到大排序，这样相同的数会排在一起；

从左到右依次枚举每个数，每次将它放在一个空位上；

对于相同数，我们人为定序，就可以避免重复计算：我们在dfs时记录一个额外的状态，记录上一个相同数存放的位置 start，我们在枚举当前数时，只枚举

start 1,start 2,…,n这些位置。

不要忘记递归前和回溯时，对状态进行更新。

时间复杂度：

搜索树中最后一层共

代码语言：txt复制

class Solution {

代码语言：txt复制

public:

代码语言：txt复制

    vector<vector<int>> res;

代码语言：txt复制

    vector<int> st, path;

代码语言：txt复制

    vector<vector<int>> permutation(vector<int>& nums) {

代码语言：txt复制

        st = vector<int>(nums.size(), false);

代码语言：txt复制

        sort(nums.begin(), nums.end());

代码语言：txt复制

        path = vector<int>(nums.size());

代码语言：txt复制

        dfs(nums, 0, 0);

代码语言：txt复制

        return res;

代码语言：txt复制

    void dfs(vector<int>& nums, int u, int start) {

代码语言：txt复制

        if(u == nums.size()) {

代码语言：txt复制

            res.push_back(path);

代码语言：txt复制

            return;

代码语言：txt复制

        if(!u || nums[u] != nums[u-1]) start = 0;

代码语言：txt复制

        for(int i=start;i<nums.size();i  ) {

代码语言：txt复制

            if (!st[i]) {

代码语言：txt复制

                st[i] = true;

代码语言：txt复制

                path[i] = nums[u];

代码语言：txt复制

                dfs(nums, u 1, i 1);

代码语言：txt复制

                // 用st[i]表示path[i]是否存在

代码语言：txt复制

                // st[i] == false，表示path[i]存在；

代码语言：txt复制

                // st[i] == true，表示path[i]不存在；

代码语言：txt复制

                // 当st[i] == false时，path[i]下次会被新的值覆盖掉，所以就不需要再remove了。

代码语言：txt复制

                st[i] = false;

代码语言：txt复制

};

另一种解法：

代码语言：txt复制

class Solution {

代码语言：txt复制

public:

代码语言：txt复制

    vector<vector<int>> res;

代码语言：txt复制

    // vector<int> st;

代码语言：txt复制

    vector<int> path;

代码语言：txt复制

    vector<vector<int>> permutation(vector<int>& nums) {

代码语言：txt复制

        // st = vector<int>(nums.size(), false);

代码语言：txt复制

        sort(nums.begin(), nums.end());

代码语言：txt复制

        // path = vector<int>(nums.size());

代码语言：txt复制

        path.resize(nums.size());

代码语言：txt复制

        dfs(nums, 0, 0, 0);

代码语言：txt复制

        return res;

代码语言：txt复制

    void dfs(vector<int>& nums, int u, int start, int state) {

代码语言：txt复制

        if(u == nums.size()) {

代码语言：txt复制

            res.push_back(path);

代码语言：txt复制

            return;

代码语言：txt复制

        if(!u|| nums[u] != nums[u-1]) start = 0;

代码语言：txt复制

        for(int i=start;i<nums.size();i  ) {

代码语言：txt复制

            if(!(state>>i&1)) {

代码语言：txt复制

                path[i] = nums[u];

代码语言：txt复制

                dfs(nums, u 1, i 1, state (1<<i));

代码语言：txt复制

};

dfs for循环

0 人点赞