Sponsored
Sponsored
This approach uses recursion combined with backtracking to generate all possible permutations of the input array. The algorithm works by swapping elements of the array and recursively building permutations by fixing one element at a time until the entire array is permutated.
Time Complexity: O(n * n!) as there are n! permutations and we copy each permutation.
Space Complexity: O(n!) for storing the permutations, plus additional space used by the recursive stack.
1using System;
2using System.Collections.Generic;
3
4public class Permutations {
5 public IList<IList<int>> Permute(int[] nums) {
6 var result = new List<IList<int>>();
7 Backtrack(nums, new List<int>(), result);
8 return result;
9 }
10
11 private void Backtrack(int[] nums, List<int> tempList, List<IList<int>> result) {
12 if (tempList.Count == nums.Length) {
13 result.Add(new List<int>(tempList));
14 } else {
15 for (int i = 0; i < nums.Length; i++) {
16 if (tempList.Contains(nums[i])) continue;
17 tempList.Add(nums[i]);
18 Backtrack(nums, tempList, result);
19 tempList.RemoveAt(tempList.Count - 1);
20 }
21 }
22 }
23
24 public static void Main(string[] args) {
25 var permutations = new Permutations();
26 int[] nums = {1, 2, 3};
27 var result = permutations.Permute(nums);
28 foreach (var perm in result) {
29 Console.WriteLine(string.Join(", ", perm));
30 }
31 }
32}
33This C# solution follows a backtracking strategy similar to other approaches. It uses a list to collect current permutations and checks to avoid reuse of elements in the current permutation by using a list of already used numbers.
An alternative iterative approach utilizes a queue to generate permutations level by level by inserting each number at every possible position within every possible permutation.
Time Complexity: O(n * n!), iterating through permutations.
Space Complexity: O(n!) for storing permutations, constant space for current permutation array.
1import
This Java implementation leverages an iterative mechanism to generate permutations by detecting and performing suitable swaps and reversals in the array, inspired by a 'next permutation' algorithm.