Permutations

                                            
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> current;
        vector<bool> used(nums.size(), false);
        backtrack(nums, current, used, result);
        return result;
    }
    
    void backtrack(vector<int>& nums, vector<int>& current, vector<bool>& used, vector<vector<int>>& result) {
        if (current.size() == nums.size()) {
            result.push_back(current);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            current.push_back(nums[i]);
            used[i] = true;
            backtrack(nums, current, used, result);
            current.pop_back();
            used[i] = false;
        }
    }
};

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

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

                                            
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(path, nums, result):
            if not nums:
                result.append(path)
            for i in range(len(nums)):
                backtrack(path + [nums[i]], nums[:i] + nums[i+1:], result)
        
        result = []
        backtrack([], nums, result)
        return result

                                            
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, 
 * assume caller calls free().
 */
int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

void backtrack(int* nums, int numsSize, int** result, int* returnSize, int level) {
    if (level == numsSize - 1) {
        int* perm = (int*)malloc(numsSize * sizeof(int));
        for (int i = 0; i < numsSize; i++) {
            perm[i] = nums[i];
        }
        result[(*returnSize)++] = perm;
        return;
    }
    for (int i = level; i < numsSize; i++) {
        int temp = nums[i];
        nums[i] = nums[level];
        nums[level] = temp;
        backtrack(nums, numsSize, result, returnSize, level + 1);
        temp = nums[i];
        nums[i] = nums[level];
        nums[level] = temp;
    }
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    int totalPermutations = factorial(numsSize);
    int** result = (int**)malloc(totalPermutations * sizeof(int*));
    *returnColumnSizes = (int*)malloc(totalPermutations * sizeof(int));
    backtrack(nums, numsSize, result, returnSize, 0);
    for (int i = 0; i < totalPermutations; i++) {
        (*returnColumnSizes)[i] = numsSize;
    }
    return result;
}

                                            
public class Solution {
    public IList<IList<int>> Permute(int[] nums) {
        IList<IList<int>> result = new List<IList<int>>();
        List<int> tempList = new List<int>();
        bool[] used = new bool[nums.Length];
        
        Backtrack(result, tempList, nums, used);
        
        return result;
    }
    
    private void Backtrack(IList<IList<int>> result, List<int> tempList, int[] nums, bool[] used) {
        if(tempList.Count == nums.Length) {
            result.Add(new List<int>(tempList));
        } else {
            for(int i = 0; i < nums.Length; i++) {
                if(used[i]) continue;
                
                tempList.Add(nums[i]);
                used[i] = true;
                Backtrack(result, tempList, nums, used);
                tempList.RemoveAt(tempList.Count - 1);
                used[i] = false;
            }
        }
    }
}

                                            
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const result = [];
    
    const backtrack = (current, remaining) => {
        if (remaining.length === 0) {
            result.push([...current]);
            return;
        }
        
        for (let i = 0; i < remaining.length; i++) {
            current.push(remaining[i]);
            backtrack(current, remaining.slice(0, i).concat(remaining.slice(i + 1)));
            current.pop();
        }
    };
    
    backtrack([], nums);
    
    return result;
};

                                            
function permute(nums: number[]): number[][] {
    const result: number[][] = [];
    
    const backtrack = (curr: number[], remaining: number[]) => {
        if (remaining.length === 0) {
            result.push(curr.slice());
            return;
        }
        
        for (let i = 0; i < remaining.length; i++) {
            curr.push(remaining[i]);
            const newRemaining = remaining.filter((_, index) => index !== i);
            backtrack(curr, newRemaining);
            curr.pop();
        }
    };
    
    backtrack([], nums);
    
    return result;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function permute($nums) {
        $result = [];
        $this->backtrack($nums, [], $result);
        return $result;
    }
    
    function backtrack($nums, $temp, &$result) {
        if (count($temp) == count($nums)) {
            $result[] = $temp;
            return;
        }
        
        for ($i = 0; $i < count($nums); $i++) {
            if (in_array($nums[$i], $temp)) continue;
            $temp[] = $nums[$i];
            $this->backtrack($nums, $temp, $result);
            array_pop($temp);
        }
    }
}

                                            
class Solution {
    func permute(_ nums: [Int]) -> [[Int]] {
        var result = [[Int]]()
        backtrack(nums, temp: [], result: &result)
        return result
    }
    
    func backtrack(_ nums: [Int], temp: [Int], result: inout [[Int]]) {
        if temp.count == nums.count {
            result.append(temp)
            return
        }
        
        for i in 0..<nums.count {
            if temp.contains(nums[i]) {
                continue
            }
            var newTemp = temp
            newTemp.append(nums[i])
            backtrack(nums, temp: newTemp, result: &result)
        }
    }
}

                                            
class Solution {
    fun permute(nums: IntArray): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        
        fun backtrack(tempList: MutableList<Int>) {
            if (tempList.size == nums.size) {
                result.add(tempList.toList())
            } else {
                for (num in nums) {
                    if (!tempList.contains(num)) {
                        tempList.add(num)
                        backtrack(tempList)
                        tempList.removeAt(tempList.size - 1)
                    }
                }
            }
        }
        
        backtrack(mutableListOf())
        
        return result
    }
}

                                            
class Solution {
  List<List<int>> permute(List<int> nums) {
    List<List<int>> result = [];
    void backtrack(int n, List<int> nums) {
      if (n == nums.length) {
        result.add(List.of(nums));
        return;
      }
      for (int i = n; i < nums.length; i++) {
        List<int> temp = List.of(nums);
        temp[n] = nums[i];
        temp[i] = nums[n];
        backtrack(n + 1, temp);
      }
    }
    backtrack(0, nums);
    return result;
  }
}

                                            
func permute(nums []int) [][]int {
    var result [][]int
    var backtrack func(start int)
    
    backtrack = func(start int) {
        if start == len(nums) {
            temp := make([]int, len(nums))
            copy(temp, nums)
            result = append(result, temp)
            return
        }
        
        for i := start; i < len(nums); i++ {
            nums[start], nums[i] = nums[i], nums[start]
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start]
        }
    }
    
    backtrack(0)
    
    return result
}

                                            
# @param {Integer[]} nums
# @return {Integer[][]}
def permute(nums)
    nums.permutation.to_a
end

                                            
object Solution {
    def permute(nums: Array[Int]): List[List[Int]] = {
        def backtrack(list: List[Int], tempList: List[Int], res: List[List[Int]]): List[List[Int]] = {
            if (tempList.length == nums.length) {
                tempList :: res
            } else {
                list.foldLeft(res) { (acc, num) =>
                    if (!tempList.contains(num)) {
                        val newTempList = num :: tempList
                        val newRes = backtrack(list, newTempList, acc)
                        newRes
                    } else {
                        acc
                    }
                }
            }
        }

        nums.permutations.map(_.toList).toList
    }
}

                                            
impl Solution {
    pub fn permute(nums: Vec<i32>) -> Vec<Vec<i32>> {
        let mut result = vec![];
        Self::backtrack(&mut result, &mut vec![], &nums);
        result
    }

    fn backtrack(result: &mut Vec<Vec<i32>>, current: &mut Vec<i32>, nums: &Vec<i32>) {
        if current.len() == nums.len() {
            result.push(current.clone());
            return;
        }

        for num in nums {
            if !current.contains(num) {
                current.push(*num);
                Self::backtrack(result, current, nums);
                current.pop();
            }
        }
    }
}

                                            
(define/contract (permute nums)
  (-> (listof exact-integer?) (listof (listof exact-integer?)))
  
  (define (permute-helper lst)
    (cond
      [(empty? lst) (list empty)]
      [else
       (for*/list ([x (in-list lst)]
                   [rest (in-list (permute-helper (remove x lst)))])
         (cons x rest))]))
  
  (permute-helper nums)
  )

                                            
-spec permute(Nums :: [integer()]) -> [[integer()]].
permute(Nums) ->
    permute([], Nums).

permute(_, []) ->
    [[]];
permute(Prefix, Suffix) ->
    [[X | Y] || X <- Suffix, Y <- permute([X | Prefix], lists:delete(X, Suffix))].

                                            
defmodule Solution do
  @spec permute(nums :: [integer]) :: [[integer]]
  def permute(nums) do
    case nums do
      [] -> [[]]
      _ -> for x <- nums, y <- permute(List.delete(nums, x)), do: [x | y]
    end
  end
end

To solve this coding challenge of finding all permutations of a given list of distinct integers, you can follow a backtracking approach. This involves recursively building the permutations by adding each available element to the current permutation path and removing it from the list of available numbers. When the list of available numbers becomes empty, a complete permutation has been formed. Here's a # Explanation section to dive deep into the problem and how we can solve it:

Explanation

This challenge asks us to generate all permutations of a list of distinct integers. A permutation of a set is a specific arrangement of its elements. For example, given the list

[1, 2, 3]

, its permutations are

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Breakdown:

Initialization:

Begin by initializing a function to start the backtracking process. This function will take an empty path that will represent the current permutation being built, the list of available numbers, and a result list to store all the permutations.

Backtracking Function:

This function will check if the list of available numbers is empty. If it is, that means a complete permutation has been formed, and we should add the current path to the result list.
Otherwise, we will iterate over the list of available numbers. For each element, we will:

Add it to the current path.
Remove it from the list of available numbers.
Recursively call the backtracking function with the updated path and list of available numbers.
After returning from the recursive call, we continue to the next element (since we are only simulating the inclusion and removal of elements).

Result Collection:

The base function will initiate the call to the backtracking function and eventually return the list of permutations collected.

With these steps in mind, here is the pseudocode for this approach:

                                            
# Function to generate all permutations of the input list
function generate_permutations(input_list):
# Initialize the result list to store all permutations
result_list = []

# Define the backtracking function
function backtrack(current_path, available_numbers, result):
# If no more numbers are available to add, a complete permutation is formed
if length of available_numbers is 0:
# Add the current permutation path to the result list
result.add(current_path)
return

# Iterate over all available numbers
for i from 0 to length of available_numbers - 1:
# Form new path including current number
new_path = current_path + [available_numbers[i]]
# Remove current number from available numbers
new_available_numbers = available_numbers[:i] + available_numbers[i+1:]
# Recursively call backtrack with the new path and updated list of numbers
backtrack(new_path, new_available_numbers, result)

# Initially call the backtracking function with an empty path
backtrack([], input_list, result_list)

# Return the complete list of permutations
return result_list

Detailed Steps in Pseudocode

Function Definition :

Define a function
generate_permutations(input_list)

to initialize the result list and start the backtracking process.

Result List Initialization :

Initialize an empty list
result_list

to store all the permutations.

Backtracking Function Definition :

Define a nested function
backtrack(current_path, available_numbers, result)

that will carry out the backtracking.

Base Case in Backtracking :

Inside the backtracking function, check if
available_numbers

is empty. If true, append
current_path

to
result

.

Iterate Through Available Numbers :

Iterate through each number in
available_numbers

.
Form a new path by adding the current number to
current_path

.
Form new available numbers by removing the current number.
Call
backtrack

with the new path and new available numbers.

Initial Call to Backtracking :

Call
backtrack

with an empty list as the initial path.

Return Result :

Return the
result_list

containing all permutations.

By following these detailed steps and using the backtracking pseudocode, you can generate all possible permutations for a list of distinct integers. Remember, the essence of the problem is to systematically explore each potential permutation path, adding each number step by step, and recursively handling the permutations by backtracking.