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.
1import java.util.ArrayList;
2import java.util.List;
3
4public class Permutations {
5 public List<List<Integer>> permute(int[] nums) {
6 List<List<Integer>> result = new ArrayList<>();
7 backtrack(nums, result, new ArrayList<Integer>(), new boolean[nums.length]);
8 return result;
9 }
10
11 private void backtrack(int[] nums, List<List<Integer>> result, List<Integer> tempList, boolean[] used) {
12 if (tempList.size() == nums.length) {
13 result.add(new ArrayList<>(tempList));
14 } else {
15 for (int i = 0; i < nums.length; i++) {
16 if (used[i]) continue;
17 used[i] = true;
18 tempList.add(nums[i]);
19 backtrack(nums, result, tempList, used);
20 used[i] = false;
21 tempList.remove(tempList.size() - 1);
22 }
23 }
24 }
25
26 public static void main(String[] args) {
27 Permutations permutations = new Permutations();
28 int[] nums = {1, 2, 3};
29 System.out.println(permutations.permute(nums));
30 }
31}
32This Java implementation uses a backtracking approach where a boolean array is used to track the numbers that have been used in the current permutation chain. The recursive mechanism generates all permutations by adding unused elements to the current list.
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.
1using System;
2using System.Collections.Generic;
public class Permutations {
public IList<IList<int>> Permute(int[] nums) {
List<IList<int>> result = new List<IList<int>>();
Array.Sort(nums);
do {
result.Add(new List<int>(nums));
} while (NextPermutation(nums));
return result;
}
private bool NextPermutation(int[] nums) {
int i = nums.Length - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--;
if (i < 0) return false;
int j = nums.Length - 1;
while (nums[j] <= nums[i]) j--;
Swap(nums, i, j);
Array.Reverse(nums, i + 1, nums.Length - i - 1);
return true;
}
private void Swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
public static void Main(string[] args) {
var permutations = new Permutations();
int[] nums = {1, 2, 3};
var result = permutations.Permute(nums);
foreach (var perm in result) {
Console.WriteLine(string.Join(", ", perm));
}
}
}
This C# solution utilizes an iteration through permutations by finding positions to create 'next permutations' without descending into recursion, applying swaps and reverses iteratively.