Backtracking - Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Explanation: All 3! = 6 permutations are returned.

Input: nums = [0,1]
Output: [[0,1],[1,0]]

We use a visited array approach. At each position in the current permutation we try every element that has not been used yet. When the current list reaches size n, we have a complete permutation.

Maintain a boolean used[] array to track which elements are in the current path.
At each recursive call, iterate over all elements; skip those already used.
Add the element, mark it used, recurse, then unmark and remove (backtrack).
When current.size() == nums.length, record the permutation.

import java.util.*; class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<>(); boolean[] used = new boolean[nums.length]; backtrack(nums, used, 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; } } }

Complexity Analysis:

Time complexity: O(n * n!) — n! permutations, each takes O(n) to copy.
Space complexity: O(n) recursion depth plus O(n * n!) for the output.