Back to Backtracking
Medium
Permutations
Given an array `nums` of distinct integers, return all the possible permutations. You can return the answer in any order.
Examples
Input:nums = [1,2,3]
Output:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
All 6 possible orderings of the 3 distinct elements are included in the result.
Input:nums = [0,1]
Output:[[0,1],[1,0]]
There are 2 possible permutations for 2 elements.
Constraints
1 <= nums.length <= 6-10 <= nums[i] <= 10All the integers of `nums` are unique.
Backtracking
Approach
We can generate all permutations by swapping elements in the array. At each step, we iterate through the remaining elements to be placed. We swap the current element with the element at the `start` index, recursively find permutations for the rest of the array, and then swap them back to restore the original state.
Complexity Analysis
Time Complexity
O(n * n!)
Space Complexity
O(n)
There are n! possible permutations. For each permutation, it takes O(n) time to copy the array to the result list. Space complexity is O(n) due to the recursion stack.
Solution.java
class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<>(); // Convert int array to Integer list for easier copying List<Integer> numsList = new ArrayList<>(); for (int num : nums) { numsList.add(num); } backtrack(0, numsList, result); return result; } private void backtrack(int start, List<Integer> nums, List<List<Integer>> result) { // Base case: we have placed all elements if (start == nums.size()) { result.add(new ArrayList<>(nums)); return; } // Explore all possible choices for the current position for (int i = start; i < nums.size(); i++) { // Swap the current element with the element at index i Collections.swap(nums, start, i); // Recurse to fill the remaining positions backtrack(start + 1, nums, result); // Backtrack: restore the array to its previous state Collections.swap(nums, start, i); } }}