Leetcode Permutations problem solution

In the Leetcode Permutations problem solution Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

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

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the integers of nums are unique.

Solution in C Programming

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
    if (numsSize == 1) {
        *returnSize = 1;
        int** output = (int**) malloc(sizeof(int*));
        *output = (int*) malloc(sizeof(int));
        *output[0] = nums[0];
        *returnColumnSizes = (int*) malloc(sizeof(int));
        *returnColumnSizes[0] = 1;
        return output;
    } else {
        int** tempOutput = permute(nums + 1, numsSize - 1, returnSize, returnColumnSizes);
        int** output = (int**) malloc(*returnSize * numsSize * sizeof(int*));
        *returnColumnSizes = (int*) malloc(*returnSize * numsSize * sizeof(int));
        for (int i = 0; i < numsSize; i++) {            
            for (int k = 0; k < *returnSize; k++) {
                int currentIndex = i * (*returnSize) + k;
                output[currentIndex] = (int*) malloc(numsSize * sizeof(int));
                for (int j = 0; j < numsSize; j++) {
                    if (i > j) {
                        output[currentIndex][j] = tempOutput[k][j];
                    } else if (i == j) {
                        output[currentIndex][j] = nums[0];
                    } else {
                        output[currentIndex][j] = tempOutput[k][j - 1];
                    }
                }
                (*returnColumnSizes)[currentIndex] = numsSize;
            }
        }
        *returnSize *= numsSize;
        return output;
    }
}

Solution in C++ Programming

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

Solution in Java Programming

class Solution {
    public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> list = new ArrayList<>();
    bt(list, new ArrayList<>(), nums);
    return list;
}

private void bt(List<List<Integer>> list, List<Integer> temp, int[] nums){
    if(temp.size() == nums.length){
        list.add(new ArrayList<>(temp));
        return;
    }
    
    for(int i=0; i< nums.length; i++){
        if(temp.contains(nums[i])){
            continue;
        }
        else{
            temp.add(nums[i]);
            bt(list, temp, nums);
            temp.remove(temp.size()-1);
        }
    }
}
}

Solution in Python Programming

class Solution(object):
    def permute(self, nums):
        ans = [nums]
        for i in xrange(1, len(nums)):
            m = len(ans)
            for k in xrange(m):
                for j in xrange(i):
                    ans.append(ans[k][:])
                    ans[-1][j], ans[-1][i] = ans[-1][i], ans[-1][j]
        return ans

Solution in C# Programming

public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        
        List<IList<int>> output = new List<IList<int>>();
        Queue<List<int>> q = new Queue<List<int>>();
        q.Enqueue(new List<int>());
        
        for(int i = 0; i < nums.Length; i++)
        {
            int n = q.Count;
            for(int j = 0; j < n; j++)
            {
                var oldPerm = q.Dequeue();
                for(int k = 0; k <= oldPerm.Count; k++)
                {
                    List<int> newPerm = new List<int>(oldPerm);
                    newPerm.Insert(k, nums[i]);
                    if(newPerm.Count == nums.Length)
                        output.Add(new List<int>(newPerm));
                    q.Enqueue(newPerm);
                }
            }
        }
        return output;        
    }
}

Also read,

By Neha Singhal

Hi, my name is Neha singhal a software engineer and coder by profession. I like to solve coding problems that give me the power to write posts for this site.

Leave a Reply

Your email address will not be published. Required fields are marked *