Description:
Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.
Examples:
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]]Solution in Python:
To solve the problem of finding all possible permutations of a list of distinct integers, we can use a backtracking approach. This involves recursively building permutations by swapping elements and backtracking to try all possible combinations.
Python
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
def backtrack(start=0):
# If we've reached the end of the array, we have a complete permutation
if start == len(nums):
result.append(nums[:]) # Append a copy of the current permutation
return
for i in range(start, len(nums)):
# Swap the current element with the start element
nums[start], nums[i] = nums[i], nums[start]
# Recursively call backtrack with the next starting index
backtrack(start + 1)
# Backtrack: undo the swap
nums[start], nums[i] = nums[i], nums[start]
result = []
backtrack()
return resultExplanation:
- Backtracking Function:
- We define a helper function
backtrack(start=0)which is used to generate permutations starting from the indexstart. - When
startequals the length ofnums, it means we have a complete permutation. We then append a copy ofnumsto theresultlist. - For each position from
startto the end of the array, we swap the element at the current position with the element at thestartposition. This effectively selects the element at the current position to be in thestartposition of the permutation. - We then recursively call
backtrackwithstart + 1to generate all permutations of the remaining elements. - After the recursive call, we swap back the elements to their original positions to backtrack and try the next possibility.
- We define a helper function
- Initialization:
- We initialize an empty list
resultto store all the permutations. - We start the backtracking process by calling
backtrack()with the default start index of 0.
- We initialize an empty list
- Example Usage:
- We create an instance of the
Solutionclass and call thepermutemethod with different test cases to verify the correctness of the solution.
- We create an instance of the
This implementation generates all possible permutations by exploring each possibility recursively and ensures that all permutations are collected in the result list. The use of backtracking allows us to efficiently explore all possible configurations.
Solution in Javascript:
JavaScript
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function(nums) {
const result = [];
// Helper function to generate permutations
const backtrack = (start = 0) => {
// If we've reached the end of the array, we have a complete permutation
if (start === nums.length) {
result.push([...nums]); // Append a copy of the current permutation
return;
}
// Iterate over the array elements to generate permutations
for (let i = start; i < nums.length; i++) {
// Swap the current element with the start element
[nums[start], nums[i]] = [nums[i], nums[start]];
// Recursively call backtrack with the next starting index
backtrack(start + 1);
// Backtrack: undo the swap to try the next possibility
[nums[start], nums[i]] = [nums[i], nums[start]];
}
};
// Start the backtracking process
backtrack();
return result;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
// Helper function to generate permutations
backtrack(nums, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, List<Integer> tempList, List<List<Integer>> result) {
// If the temporary list has reached the size of the original array, we have a complete permutation
if (tempList.size() == nums.length) {
result.add(new ArrayList<>(tempList)); // Add a copy of the current permutation to the result list
} else {
// Iterate over the array elements to generate permutations
for (int i = 0; i < nums.length; i++) {
// Skip elements that are already in the temporary list
if (tempList.contains(nums[i])) continue;
// Add the current element to the temporary list
tempList.add(nums[i]);
// Recursively call backtrack to continue generating the permutation
backtrack(nums, tempList, result);
// Backtrack: remove the last element added to try the next possibility
tempList.remove(tempList.size() - 1);
}
}
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> Permute(int[] nums) {
IList<IList<int>> result = new List<IList<int>>();
// Helper function to generate permutations
Backtrack(nums, new List<int>(), result);
return result;
}
private void Backtrack(int[] nums, List<int> tempList, IList<IList<int>> result) {
// If the temporary list has reached the size of the original array, we have a complete permutation
if (tempList.Count == nums.Length) {
result.Add(new List<int>(tempList)); // Add a copy of the current permutation to the result list
} else {
// Iterate over the array elements to generate permutations
for (int i = 0; i < nums.Length; i++) {
// Skip elements that are already in the temporary list
if (tempList.Contains(nums[i])) continue;
// Add the current element to the temporary list
tempList.Add(nums[i]);
// Recursively call Backtrack to continue generating the permutation
Backtrack(nums, tempList, result);
// Backtrack: remove the last element added to try the next possibility
tempList.RemoveAt(tempList.Count - 1);
}
}
}
}