# 四种语言刷算法之全排列()-其他

## 四种语言刷算法之全排列()

1、C

/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
void back(int *nums,int numsSize,int* returnSize, int** returnColumnSizes,int *visited,int *path,int *pathSize,int **result){
if(*pathSize==numsSize){
result[*returnSize] = (int *)malloc(sizeof(int)*numsSize);
memcpy(result[*returnSize], path, sizeof(int) * numsSize);
(*returnColumnSizes)[*returnSize] = numsSize;
(*returnSize)++;
return;
}
for(int i=0;i<numsSize;i++){
if (visited[i] == 1) {
continue;
}
path[*pathSize] = nums[i];
(*pathSize)++;
visited[i] = 1;
back(nums,numsSize,returnSize,returnColumnSizes,visited,path,pathSize,result);
(*pathSize)--;
visited[i] = 0;
}
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
*returnSize = 0;
*returnColumnSizes = (int*)malloc(sizeof(int) * 100001);
int *visited = (int *)calloc(numsSize,sizeof(int));
int *path = (int *)malloc(sizeof(int)*numsSize);
int *pathSize = (int *)calloc(1,sizeof(int));
int **result = (int **)malloc(sizeof(int*)*100001);
back(nums,numsSize,returnSize,returnColumnSizes,visited,path,pathSize,result);
return result;
}

2、C++

class Solution {
public:
void back(vector<int> &nums,vector<bool> &visited,vector<vector<int>> &result,vector<int> &path){
if(path.size()==nums.size()){
result.push_back(path);
return;
}
for(int i=0;i<nums.size();i++){
if(visited[i]){
continue;
}
path.push_back(nums[i]);
visited[i] = true;
back(nums,visited,result,path);
path.pop_back();
visited[i] = false;
}

}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> path;
vector<bool> visited(nums.size(),false);
back(nums,visited,result,path);
return result;
}
};

3、JAVA

class Solution {
List<List<Integer>> result = new ArrayList<>();
private void back(int[] nums,boolean[] visited){
if(nums.length == path.size()){
return;
}
for(int i =0;i<nums.length;i++){
if(visited[i]){
continue;
}
visited[i] = true;
back(nums,visited);
path.removeLast();
visited[i] = false;
}
}
public List<List<Integer>> permute(int[] nums) {
boolean visited[] = new boolean[nums.length];
back(nums,visited);
return result;
}
}

4、Python

class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
visited = [False] * len(nums)
path = []
result = []
self.back(nums,visited,path,result)
return result

def back(self,nums,visited,path,result):
if len(path)==len(nums):
result.append(path[:])
return
for i in range(0,len(nums)):
if visited[i]:
continue;
path.append(nums[i])
visited[i] = True
self.back(nums,visited,path,result)
path.pop()
visited[i] = False
————————

1、C

/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
void back(int *nums,int numsSize,int* returnSize, int** returnColumnSizes,int *visited,int *path,int *pathSize,int **result){
if(*pathSize==numsSize){
result[*returnSize] = (int *)malloc(sizeof(int)*numsSize);
memcpy(result[*returnSize], path, sizeof(int) * numsSize);
(*returnColumnSizes)[*returnSize] = numsSize;
(*returnSize)++;
return;
}
for(int i=0;i<numsSize;i++){
if (visited[i] == 1) {
continue;
}
path[*pathSize] = nums[i];
(*pathSize)++;
visited[i] = 1;
back(nums,numsSize,returnSize,returnColumnSizes,visited,path,pathSize,result);
(*pathSize)--;
visited[i] = 0;
}
}
int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
*returnSize = 0;
*returnColumnSizes = (int*)malloc(sizeof(int) * 100001);
int *visited = (int *)calloc(numsSize,sizeof(int));
int *path = (int *)malloc(sizeof(int)*numsSize);
int *pathSize = (int *)calloc(1,sizeof(int));
int **result = (int **)malloc(sizeof(int*)*100001);
back(nums,numsSize,returnSize,returnColumnSizes,visited,path,pathSize,result);
return result;
}

2、C++

class Solution {
public:
void back(vector<int> &nums,vector<bool> &visited,vector<vector<int>> &result,vector<int> &path){
if(path.size()==nums.size()){
result.push_back(path);
return;
}
for(int i=0;i<nums.size();i++){
if(visited[i]){
continue;
}
path.push_back(nums[i]);
visited[i] = true;
back(nums,visited,result,path);
path.pop_back();
visited[i] = false;
}

}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;
vector<int> path;
vector<bool> visited(nums.size(),false);
back(nums,visited,result,path);
return result;
}
};

3、JAVA

class Solution {
List<List<Integer>> result = new ArrayList<>();
private void back(int[] nums,boolean[] visited){
if(nums.length == path.size()){
return;
}
for(int i =0;i<nums.length;i++){
if(visited[i]){
continue;
}
visited[i] = true;
back(nums,visited);
path.removeLast();
visited[i] = false;
}
}
public List<List<Integer>> permute(int[] nums) {
boolean visited[] = new boolean[nums.length];
back(nums,visited);
return result;
}
}

4、Python

class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
visited = [False] * len(nums)
path = []
result = []
self.back(nums,visited,path,result)
return result

def back(self,nums,visited,path,result):
if len(path)==len(nums):
result.append(path[:])
return
for i in range(0,len(nums)):
if visited[i]:
continue;
path.append(nums[i])
visited[i] = True
self.back(nums,visited,path,result)
path.pop()
visited[i] = False