LeetCode #46: Permutations — Solved in Java
Backtracking and In-Place Swapping
LeetCode 46, Permutations, asks you to take an array of distinct integers and produce every possible ordering of those numbers. Each ordering is called a permutation, and the result that permute returns is a list that contains all of them, with each permutation stored as its own list of integers. Input values stay the same, only their positions change, and no duplicates appear in the output because the input does not repeat any number.
When you work on this problem in Java, it helps to think about what state needs to be tracked while permute builds those permutations. One natural strategy is to picture a growing sequence that records choices made so far and some structure that says which indices are already used, which leads directly to a backtracking method that tries candidates, recurses, then undoes the choice. A different way of thinking keeps everything inside the original array and moves values around with swaps, treating a prefix as fixed and the rest as positions waiting to be filled. Both views rely on Java arrays, ArrayList, and recursion, so reading the code with state changes in mind will make the control flow and later complexity analysis much easier to follow.
Given an array
numsof distinct integers, return all the possible permutations (A permutation is a rearrangement of all the elements of an array). You can return the answer in any order.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]]Example 2:
Input: nums = [0,1] Output: [[0,1],[1,0]]Example 3:
Input: nums = [1] Output: [[1]]Constraints:
1 <= nums.length <= 6
-10 <= nums[i] <= 10All the integers of
numsare unique.
Solution 1: Backtracking With Used Markers
This solution builds permutations by growing one choice sequence step by step and keeping track of which indices in nums are already included. For each position in the current sequence, the code scans through all indices, skips any index that is already used, and appends any unused value, then recurses. When the sequence reaches length n, that sequence is copied into the result list. Backtracking then removes the last value and marks its index as unused, which lets other choices be tried at that position.
