Given an array nums of distinct integers, return all possible permutations.
Example 1
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 orderings.
1 <= nums.length <= 6Unlike Subsets, order matters here — [1,2] and [2,1] are different, distinct answers.
Track which elements are already 'used' in the current permutation-in-progress — the recursion considers every UNUSED element at each position, not a start index.
A result is only complete (added to the answer list) when the current permutation reaches the full length of nums — unlike Subsets, where every partial state was already valid.
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, new ArrayList<>(), new boolean[nums.length], result);
return result;
}
private void backtrack(int[] nums, List<Integer> current, boolean[] used, List<List<Integer>> result) {
if (current.size() == nums.length) { // ONLY a complete permutation counts — unlike Subsets
result.add(new ArrayList<>(current));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) continue; // skip elements already placed in this permutation
used[i] = true;
current.add(nums[i]);
backtrack(nums, current, used, result);
current.remove(current.size() - 1); // UNCHOOSE
used[i] = false; // UNCHOOSE
}
}Time: O(n * n!) · Space: O(n) recursion depth, excluding output