四种语言刷算法之全排列

力扣46.全排列

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<>();
    LinkedList<Integer> path = new LinkedList<>();
    private void back(int[] nums,boolean[] visited){
        if(nums.length == path.size()){
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i =0;i<nums.length;i++){
            if(visited[i]){
                continue;
            }
            visited[i] = true;
            path.add(nums[i]);
            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