Leecode热题100---46：全排列（递归）

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

思路：
元素交换+函数递归：
通过交换元素来实现全排列。即对于[x, nums.size()]中的元素，for循环遍历每个元素分别成为第一个元素；
然后再对[x + 1, nums.size()-1)递归调用排列函数，直到 x == nums.size()-1 递归终止。

C++：

#include<iostream>
#include<vector>
using namespace std;class Soluiton
{
private:vector<vector<>int>res;//通过交换元素来实现全排列。即对于[x, nums.size()]中的元素，for循环遍历每个元素分别成为第一个元素，//然后再对[x + 1, end-1)递归调用排列函数，直到 x == nums.size()-1 递归终止。void dfs(vector<int>nums,int x){if(x == nums.size() - 1){res.push_back(nums);	//添加排列方案return;}for(int i = x;i<nums.size(); i++){swap(nums[i],nums[x]);	// 交换，将nums[i]固定在第x位dfs(nums,x+1);			// 开启固定第 x+1 位元素swap(nums[i],nums[x]);	// 恢复交换}}public:vector<vector<int>> permute(vector<int>& nums){dfs(nums,0);return res;}
};

python:

class Solution:def permute(self,nums):res = []def dfs(x):if x == len(nums)-1:res.append(list(nums))      # 添加排列方案returnfor i in range(x,len(nums)):nums[i], nums[x] = nums[x], nums[i]     # 交换，将 nums[i] 固定在第 x 位dfs(x+1)                                # 开启固定第 x + 1 位元素nums[i], nums[x] = nums[x], nums[i]     # 恢复交换dfs(0)return res