Permutations Problem Solution

Permutations Problem: Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example :

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Permutations Problem Solution

Problem Solution In Python

def permute(self, nums):
    if not nums: 
       return [[]]
    return [[nums[i]] + j for i in xrange(len(nums)) for j in self.permute(nums[:i]+nums[i+1:])]

Problem Solution In Java

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> ds = new ArrayList<>();
        boolean[] freq = new boolean[nums.length];
        fun(nums, ds,ans, freq);
        return ans;
    }
    public void fun(int[] nums,List<Integer> ds,List<List<Integer>> ans,boolean[] freq){
        if(ds.size()==nums.length){
            ans.add(new ArrayList<>(ds));
            return ;
        }
        for(int i=0;i<nums.length;i++){
            if(!freq[i]){
                freq[i] = true;
                ds.add(nums[i]);
                fun(nums, ds,ans, freq);
                ds.remove(ds.size()-1);
                freq[i] = false;
            }
        }
    }
}

Problem Solution In C++

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

Problem Solution In C

void permute_step(int* p, int n, int* k,int** rp,int nn)
{
    int tmp;
    if (n == 1)
    {
        rp[*k][n - 1] = p[0];
        for (int i = 0;i < nn;i++)
        {   
            if (rp[*k][i] <= -1024) rp[*k][i] = rp[(*k) - 1][i];
        }
        (*k)++;
    }
    else
    {
        for (int i = 0;i < n;i++)
        {
            rp[*k][n - 1] = p[i];tmp = p[i];p[i] = p[0];
            permute_step(p + 1, n - 1, k, rp, nn);
            p[0] = p[i];p[i] = tmp;
        }
    }
}

int** permute(int* nums, int numsSize, int* returnSize) {
    *returnSize = 1;
    for (int i = 1;i <= numsSize;i++)
        *returnSize *= i;
    int** r = (int**)malloc(sizeof(int*)*(*returnSize));
    for (int i = 0;i < *returnSize;i++)
    {
        r[i] = (int*)malloc(sizeof(int)*numsSize);
        for (int j = 0;j < numsSize;j++)
            r[i][j] = -1024;
    }
    int k = 0;int* kp = &k;
    permute_step(nums, numsSize, kp, r, numsSize);
    return r;
}