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
numsare 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;
}
Input
nums = [1,2,3]
Output
[[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]>;
}
}
};
Input
nums = [0,1]
Output
[[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);
}
}
}
}
}
Input
nums = [1]
Output
[[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();
}
}
}
Input
nums = [1,2,3]
Output
[[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))
Input
nums = [0,1]
Output
[[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;
}
}
}
Input
nums = [1]
Output
[[1]]