Leetcode 46.全排列【C++】

地址：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++;
        }
    }
};