【LeetCode-中等】46. 全排列 - 回溯

46. 全排列

解法：回溯
回溯法：一种通过探索所有可能的候选解来找出所有的解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会通过在上一步进行一些变化抛弃该解，即回溯并且再次尝试。
详解见：题解

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        int len=nums.size();
        backtrack(res,nums,0,len);
        return res;
    }
    void backtrack(vector<vector<int>>& res,vector<int>& output,int first,int len){
        //所有数都填完了
        if(first==len){
            res.emplace_back(output);
            return;
        }
        for(int i=first;i<len;i++){
            //动态维护数组
            swap(output[i],output[first]);
            //继续递归填下一个数
            backtrack(res,output,first+1,len);
            //撤销操作
            swap(output[i],output[first]);
        }
    }
};