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;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment