0%

[0046] 全排列

发表于 更新于 分类于 ， 本文字数： 1.3k 阅读时长 ≈ 1 分钟
...

[0046] 全排列

题目描述

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Related Topics
  • 回溯算法

    • 题目解析

    • 模拟选择法解决该问题

    不确定性

    • 数据的长度, 会不会为0

    方法一：模拟选择法

    分析

    每次从剩下的数字里选择一个数据当作第一个，再去求解剩下序列中的所有排列。

    思路

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    permutation(set, selected) {
      if len(set)==0 { res.add(selected) return} // 所有数字都选择完毕，加入一个可行解
      for n in set {
        selected.add(n)
        set.remove(n) 
        permutation(set, selected)
       
        set.add(n)
        selected.remove(n)
      }
    }

    注意

    • 终止条件判断

    知识点

    • dfs
    • 模拟排列选择

    复杂度

    • 空间复杂度O(n)
    • 时间复杂度O(n!)

    代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    class Solution {
    private:
        vector<bool> vis;
        vector<vector<int> > res;
        void dfs(int dep, int n,vector<int> & selected, vector<int> & nums) {
            if (dep==n) {
                res.push_back(selected);
                return;
            }

            for (int i=0;i<n;i++) {
                if (vis[i])continue;
                vis[i]=true;
                selected.push_back(nums[i]);
                dfs(dep+1, n, selected, nums);
                selected.pop_back();
                vis[i]= false;
            }
        }
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            res.clear();
            int n=nums.size();
            vector<int> selected;
            vis.assign(n, false);
            dfs(0, n, selected, nums);

            return res;
        }
    };

    /*
    [1,2,3]
    []
    */

    相关题目

    相关文章