Permutations
Given an array of distinct integers, return all possible permutations of the array. The output should be a list of lists, where each sublist is a permutation of the input array.
Constraints:
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
Examples:
Input: [1, 2, 3]
Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Explanation: The input array [1, 2, 3] has 6 possible permutations, which are listed in the output.
Solutions
Backtracking
The backtracking approach is used to generate all permutations of the input array. The backtrack function takes two parameters, start and end, which represent the current range of the array being processed. If start equals end, it means we have reached the end of the current permutation, so we add it to the result list. Otherwise, we iterate over the range from start to end, swap the current element with the start element, and recursively call the backtrack function with the updated range. After the recursive call returns, we swap the elements back to restore the original array.
function permute(nums) {
let res = [];
function backtrack(start, end) {
if (start === end) {
res.push([...nums]);
}
for (let i = start; i < end; i++) {
[nums[start], nums[i]] = [nums[i], nums[start]];
backtrack(start + 1, end);
[nums[start], nums[i]] = [nums[i], nums[start]];
}
}
backtrack(0, nums.length);
return res;
}
Follow-up:
How would you optimize the solution to handle larger input arrays?
