【LeetCode】46. 全排列

题目

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

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

思路一:STL

next_permutation使用前需要先排序,否则只能找出该序列之后的全排列数。

代码

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        if (nums.empty()) return res;
        sort(nums.begin(), nums.end());
        res.push_back(nums);
        while (next_permutation(nums.begin(), nums.end())) {
            res.push_back(nums);
        }
        return res;
    }
};

思路二:回溯

  • 对于两个数[4, 5],全排列为4 5 和 5 4 ,即以4开头全排列和以5开头全排列,一个数全排列即为本身。
  • 对于三个数[3, 4, 5], 全排列为:
    3 4 5
    3 5 4
    4 3 5
    4 5 3
    5 3 4
    5 4 3
    即分别以3、4、5开头的全排列,可以看作数组中所有数分别和第一个数交换,然后处理后面n - 1个数的排列。

代码

时间复杂度:O(n * n!)
空间复杂度:O(n)

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        if (nums.empty()) return res;
        dfs(nums, res, 0);
        return res;
    }

    void dfs(vector<int> &nums, vector<vector<int>> &res, int i) {
        if (i == nums.size()) {           
            res.push_back(nums);
        }
        for (int j = i; j < nums.size(); ++j) {
            swap(nums[j], nums[i]);
            dfs(nums, res, i + 1);
            swap(nums[j], nums[i]);//回溯
        }
    }
};
上一篇:通过Dockerfile来部署datax容器


下一篇:[每日一题2020.06.24]leetcode #46 dfs