回溯算法--全排列（leetcode 46）

——个人学习笔记

-全排列（没相同数字）

参考题目：https://leetcode-cn.com/problems/permutations/comments/

• 解法一（C++）：
  • 思路：以数组下标位置为标记k，循环体结束条件为遍历整个数组。循环主体是每一个位置都和后面以及自身各个数交换，获取新的排列，回溯就是把交换的再换回原来的数组。例如：123， 第一次1自己交换进入递归，第一层递归2自己交换进入递归，第二层递归回溯并返回123，然后回溯到第一层递归2又跟3交换进入递归，第二层递归再次回溯并返回132。接着在第一层递归3和2交换回来接着回溯到第一次。这就是完整的一次，然后到1和2交换，1和3交换过程一样
  • 图（·为层数，num的值为执行完那次递归的最后值）：
  • 代码：

 class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        permuteNum(0,nums,result);
        return result;
    }
    
    
    void  permuteNum(int k,vector<int>& nums,vector<vector<int>>&res)
    {
        if(k==nums.size())
        {
            res.push_back(nums);
            return ;
        }
        for(int i=k;i<nums.size();i++)
        {
            swap(nums[k],nums[i]);
            permuteNum(k+1,nums,res);
            swap(nums[k],nums[i]);   
        }
    }
};

• 解法二（C++）：
  • 思路：用一个bool数组来记录该位置的数字是否已经选取过，采用深度优先搜索的方法来做。
  • 代码可参考：https://blog.csdn.net/Scarlett_Guan/article/details/80031615