Back to DSA
Permutations
mediumGiven an array of distinct integers, generate every possible ordering (permutation) of those integers. The results may appear in any sequence.
Examples
Example 1:
Input:
nums = [7,8,9]Output:
[[7,8,9],[7,9,8],[8,7,9],[8,9,7],[9,7,8],[9,8,7]] Example 2:
Input:
nums = [4,5]Output:
[[4,5],[5,4]]Hints
import java.util.*;
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, new boolean[nums.length], new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, boolean[] used, List<Integer> current, List<List<Integer>> result) {
if (current.size() == nums.length) { result.add(new ArrayList<>(current)); return; }
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
current.add(nums[i]);
backtrack(nums, used, current, result);
current.remove(current.size() - 1);
used[i] = false;
}
}
}Time complexity
O(n * n!)Space complexity
O(n)