46. Permutations#

 1public List<List<Integer>> permute(int[] nums) {
 2  List<List<Integer>> result = new ArrayList<>();
 3  List<Integer> path = new ArrayList<>();
 4  boolean[] used = new boolean[nums.length];
 5
 6  backtrack(nums, result, path, used);
 7
 8  return result;
 9}
10
11private void backtrack(
12  int[] nums,
13  List<List<Integer>> result,
14  List<Integer> path,
15  boolean[] used
16) {
17  if (path.size() == nums.length) {
18    result.add(List.copyOf(path));
19  }
20
21  for (int i = 0; i < nums.length; i++) {
22    if (!used[i]) {
23      path.add(nums[i]);
24      used[i] = true;
25      backtrack(nums, result, path, used);
26      path.remove(path.size() - 1);
27      used[i] = false;
28    }
29  }
30}

Time Complexity

Space Complexity

\(\mathcal{O}(n!)\)

\(\mathcal{O}(n)\)