[C++知识库]46 全排列（c++ 回溯实现）

题目

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列 。你可以按任意顺序返回答案。

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

class Solution {
public:
    vector<vector<int>> result;//记录最终的全排列结果
    vector<int> path;//记录一个全排列结果
    
    void backtracking(vector<int>& nums, vector<bool>& used, int index){//当前处理排列的第index号位
        if(path.size() == nums.size()){//递归边界，已获得一个全排列
            result.push_back(path);//将该全排列加入到结果中
            return;
        }
        for(int i = 0; i < nums.size(); i++){//逐个枚举，试图将该数填入到path[i]中
            if(used[i] == false){//如果该数还未被使用，即不再当前排列中
            used[i] = true;//记录该数在排列中
            path.push_back(nums[i]);//将该数加入到排列中
            backtracking(nums, used, index+1);//处理nums的第index+1号位
            path.pop_back();
            used[i] = false;//已处理完path[i]的子问题，恢复状态
            }
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        result.clear();
        path.clear();
        vector<bool> used(nums.size(), false);//记录nums中的数是否已在排列中
        backtracking(nums, used, 0);//从0号位开始处理
        return result;
    }
};

• 全排列问题
  • 指n个数所能形成的所以排列
  • 如果要按字典序输出排列结果，只需先对nums做一次自小到大排序
• 思路
  • 如果把问题描述成“输出这n个数字的全排列”，那么它就可以被分解为若干个子问题。输出以第一个数为首的全排列，输出以第二个数为首的全排列，…，输出以第n个数为首的全排列。
  • 定义一个向量path存储当前的排列，再定义一个向量used标记nums中的数是否已经被填入到path中，used[i]为true表示nums[i]已经在path中了
  • 现在按顺序往path的第一位到第n位填数字。假设当前已经填好了path[0] ~ path[index - 1], 现在要填path[index]。
  • 枚举此时nums中的数字，如果它还没有在path中，就将它加入path，同时将used[i]设置为true。
  • 然后去填path的下一位，即进行递归。
  • 当递归完成时，再将used[i]还原为false，同时将path的末尾元素弹出。
  • 递归边界为完成一次全排列，即path的长度和nums的长度一致，此时返回。