Algorithm


Problem Name: 46. Permutations

Problem Link: https://leetcode.com/problems/permutations/
 

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]]

Example 3:

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

Constraints:

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

Code Examples

#1 Code Example with C Programming

Code - C Programming


void bt(int **p, int *buff, int *v, int *nums, int sz, int l, int *n) {
  int i;

    if (l == sz) {
    p[*n] = malloc(sz * sizeof(int));
    //assert(p[k]);
    memcpy(p[*n], buff, sz * sizeof(int));
      (*n) ++;
    return;
    }
    for (i = 0; i  <  sz; i ++) {
    if (!v[i]) {
        v[i] = 1;
        buff[l] = nums[i];
        bt(p, buff, v, nums, sz, l + 1, n);
        v[i] = 0;
      }
    }
}
int** permute(int* nums, int numsSize, int* returnSize) {
  int *buff, **p, *v;
  int i, n;
  n = 1;
  for (i = 2; i  < = numsSize; i ++) {
    n = n * i;
  }
  *returnSize = n;
  p = malloc(n * sizeof(int *));
  v = calloc(numsSize, sizeof(int));
  buff = malloc(numsSize * sizeof(int));
  //assert(p && v && buff);
  
  n = 0;
  bt(p, buff, v, nums, numsSize, 0, &n);
  
  free(buff); free(v);
  
  return p;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,2,3]

Output

x
+
cmd
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

#2 Code Example with C++ Programming

Code - 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);
            swap(nums[pos], nums[i]>;
        }
    }
};
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [0,1]

Output

x
+
cmd
[[0,1],[1,0]]

#3 Code Example with Java Programming

Code - Java Programming


class Solution {
  public List();
    helper(nums, result, new ArrayList<>(), new boolean[nums.length]);
    return result;
  }
  
  private void helper(int[] nums, List < List curr, boolean[] visited) {
    if (curr.size() == nums.length) {
      result.add(new ArrayList<>(curr));
    } else {
      for (int i = 0; i  <  nums.length; i++) {
        if (!visited[i]) {
          visited[i] = true;
          curr.add(nums[i]);
          helper(nums, result, curr, visited);
          visited[i] = false;
          curr.remove(curr.size() - 1);
        }
      }
    }
  }
}

Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1]

Output

x
+
cmd
[[1]]

#4 Code Example with Javascript Programming

Code - Javascript Programming


function permute(nums) {
  const list = [];
  // Arrays.sort(nums); // not necessary
  backtrack(list, [], nums);
  return list;
}

function backtrack(list, tempList, nums) {
  if (tempList.length == nums.length) {
    list.push(tempList.slice(0));
  } else {
    for (let i = 0; i  <  nums.length; i++) {
      if (tempList.includes(nums[i])) continue; // element already exists, skip
      tempList.push(nums[i]);
      backtrack(list, tempList, nums);
      tempList.pop();
    }
  }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1,2,3]

Output

x
+
cmd
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

#5 Code Example with Python Programming

Code - Python Programming


class Solution:
    def permute(self, nums): return list(itertools.permutations(nums))
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [0,1]

Output

x
+
cmd
[[0,1],[1,0]]

#6 Code Example with C# Programming

Code - C# Programming


using System.Collections.Generic;

namespace LeetCode
{
    public class _046_Permutations
    {
        public IList < IList<int>> Permute(int[] nums)
        {
            var result = new List < IList<int>>();
            result.Add(nums);

            int length = nums.Length;
            int size, temp, i, j, k;
            IList < int> tempList;
            for (i = 0; i  <  length; i++)
            {
                size = result.Count;
                for (j = 0; j  <  size; j++)
                {
                    for (k = i + 1; k  <  length; k++)
                    {
                        tempList = new List<int>(result[j]);
                        temp = tempList[k];
                        tempList[k] = tempList[i];
                        tempList[i] = temp;
                        result.Add(tempList);
                    }
                }
            }

            return result;
        }
    }
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
nums = [1]

Output

x
+
cmd
[[1]]
Advertisements

Demonstration


Previous
#45 Leetcode Jump Game II Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#47 Leetcode Permutations II Solution in C, C++, Java, JavaScript, Python, C# Leetcode