本文最后更新于:2020年4月25日 晚上

地址:https://leetcode-cn.com/problems/permutations/

题目

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

示例:

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

解题思路

其实按照我们人的思维很容易想到,全排列就是每次从剩余的数字里面取一个数字,只要保证相同的操作就可以了,但是要写代码来求解还是有些不太一样的。起初我试图找到一点什么规律,比如,知道数组的长度 n 其实就可以确定不同全排列的个数为 n! ,但是对解题并没什么益处。

后来再一想,动态规划?感觉不行,虽然可以一个数一个数的取,但是由于最重要得到所有可能的全排列,所以意味着我们没取一个数,都要将取这个数所能构成的所有全排列保存下来,这个工作是很复杂的。

其实应该用回溯法,因为我们每取一个数出来排列,都会影响下一次能取到的数。以 [1,2,3] 为例,第一次我们可以取三个数中的任意一个,也就是我们可以用一个循环 for x in [1,2,3] 取依次取三个数中的一个,假如我们取了 1 ,则剩下可取的为 [2,3] ,重复上述步骤,直到没有可取的数了,即找到了一个全排列。

不同的全排列即我们每一步取数的路径,所以递归函数中需要用一个引用型参数用于记录路径,找到一个全排列,就将其加入到要求的返回结果中。

附上 labuladong 的回溯算法框架:

result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

代码

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;//路径
        backtrack(ans, nums, path);
        return ans;
    }

    void backtrack(vector<vector<int>>& ans, vector<int>& nums, vector<int>& path) {
        if (nums.empty()) {
            ans.push_back(path);
            return;
        }
        int i = 0;
        while (i < nums.size())
        {
            //做选择
            path.push_back(nums[i]);
            nums.erase(nums.begin() + i);
            //回溯
            backtrack(ans, nums, path);
            //撤销选择
            nums.insert(nums.begin() + i, path.back());
            path.pop_back();
            i++;
        }
    }
};