Permutations of an Array — Problem Statement & Solution Guide
Problem Description
Given an array of distinct integers, generate the complete set of all possible orderings (permutations) of the elements. A permutation is defined as a rearrangement of all elements in the array such that each element appears exactly once in every resulting sequence. The order of the returned permutations does not matter, but the set must be exhaustive and contain no duplicates.
Input: An array 'nums' containing distinct integers.
Output: A list of lists, where each inner list represents a unique permutation of the input array. If the input array is empty, return an empty list.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Permutations of an Array"
WHY DOES IT MATTER?
This pattern is the foundation for solving many combinatorial problems such as combinations, subsets, and next permutation. Mastering backtracking with state management (tracking used elements) is essential for handling problems where the order of selection matters and the search space is exponential.
OPTIMIZATION CHALLENGE
The key optimization is avoiding the creation of new arrays at every recursive step. By using in-place swapping or a shared mutable state with careful backtracking (undoing changes after recursion), we reduce space complexity from O(N * N!) to O(N) for the recursion stack plus O(N) for the current path.
REAL-WORLD CONNECTION
This is analogous to scheduling tasks in a distributed system where every possible order of execution must be evaluated for optimization, or in cryptography where key spaces are explored. It also relates to route planning in logistics where all possible delivery sequences are considered to find the optimal path.
During the interview, explicitly mention the trade-off between using a 'used' boolean array versus in-place swapping. The 'used' array is easier to reason about and less error-prone, while in-place swapping is more memory-efficient. Choose based on the interviewer's preference for clarity vs. optimization.
COMPLEXITY AT A GLANCE
O(N * N!)O(N)Core Theory — Why This Approach?
Generating all permutations of an array is a classic combinatorial problem that fundamentally relies on backtracking. The core intuition is to fix one element at a time and recursively generate permutations for the remaining elements. For an array of size N, there are N! (N factorial) possible permutations. A naive recursive approach that creates a new array for every recursive call leads to significant memory overhead and time complexity due to constant copying. The optimal paradigm involves in-place swapping or using a 'used' boolean array to track which elements have been included in the current path, allowing us to build the permutation incrementally without unnecessary data duplication.
Interview Questions on This Problem
Q1How would you modify the permutation algorithm to handle an array with duplicate elements, ensuring no duplicate permutations are generated?
To handle duplicates, sort the array first. Then, during the backtracking process, skip an element if it is the same as the previous element and the previous element was not used in the current recursion level. This pruning step ensures that identical branches are not explored multiple times, reducing the effective branching factor.
Q2What is the time complexity of generating all permutations, and why can it not be improved asymptotically?
The time complexity is O(N * N!). This is because there are N! permutations, and generating each permutation requires O(N) time to copy the current state into the result list. Since the output size itself is N!, the algorithm is optimal in terms of output sensitivity; you cannot generate N! items in less than O(N!) time.
Q3In a distributed system, how would you parallelize the generation of permutations to utilize multiple cores?
You can parallelize at the top level of the recursion. For the first element, there are N choices. You can assign each of the N branches to a different thread or worker process. Each worker then recursively generates the permutations for the remaining N-1 elements. This divides the workload evenly and leverages the independent nature of the first-level branches.
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]]
Explanation: The array has 3 distinct elements, so there are 3! = 6 permutations. 1. Fix 1 at the start: Permute [2, 3] -> [1, 2, 3], [1, 3, 2]. 2. Fix 2 at the start: Permute [1, 3] -> [2, 1, 3], [2, 3, 1]. 3. Fix 3 at the start: Permute [1, 2] -> [3, 1, 2], [3, 2, 1]. Combining these yields the 6 unique permutations.
Input
nums = [4, 5]
Output
[[4, 5], [5, 4]]
Explanation: The array has 2 distinct elements, so there are 2! = 2 permutations. 1. Fix 4 at the start: Remaining is [5] -> [4, 5]. 2. Fix 5 at the start: Remaining is [4] -> [5, 4]. These are the only two possible orderings.
Input
nums = [7]
Output
[[7]]
Explanation: The array has 1 element, so there is 1! = 1 permutation. The only possible ordering is the element itself: [7].
Input
nums = [10, 20, 30, 40]
Output
[[10, 20, 30, 40], [10, 20, 40, 30], [10, 30, 20, 40], [10, 30, 40, 20], [10, 40, 20, 30], [10, 40, 30, 20], [20, 10, 30, 40], [20, 10, 40, 30], [20, 30, 10, 40], [20, 30, 40, 10], [20, 40, 10, 30], [20, 40, 30, 10], [30, 10, 20, 40], [30, 10, 40, 20], [30, 20, 10, 40], [30, 20, 40, 10], [30, 40, 10, 20], [30, 40, 20, 10], [40, 10, 20, 30], [40, 10, 30, 20], [40, 20, 10, 30], [40, 20, 30, 10], [40, 30, 10, 20], [40, 30, 20, 10]]
Explanation: The array has 4 distinct elements, so there are 4! = 24 permutations. The output lists all 24 unique sequences formed by rearranging 10, 20, 30, and 40. For instance, fixing 10 first generates 3! = 6 permutations of the remaining [20, 30, 40]. This process repeats for 20, 30, and 40, totaling 24 unique permutations.
Constraints
- 1 <= nums.length <= 8
- -100 <= nums[i] <= 100
- All integers in nums are distinct.
Optimal Approach & Strategy
The optimized approach uses backtracking with a 'used' boolean array to track which elements are currently in the path. By only considering unused elements at each step, we directly generate valid permutations without validation, reducing the constant factor and avoiding unnecessary work.
Brute Force Approach
A brute force approach would involve generating all possible sequences of indices from 0 to N-1 and checking if each sequence is a valid permutation (i.e., contains each index exactly once). This is inefficient because it generates many invalid sequences and requires O(N) validation for each of the N! valid ones.
Verified Code Solutions
function permute(nums) { let result = []; function backtrack(start, end) { if (start === end) { result.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 result; }class Solution { public: vector<vector<int>> permute(vector<int>& nums) { vector<vector<int>> result; vector<int> temp; backtrack(result, temp, nums, 0); return result; } private: void backtrack(vector<vector<int>>& result, vector<int>& temp, vector<int>& nums, int start) { if (start == nums.size()) { result.push_back(temp); } for (int i = start; i < nums.size(); i++) { swap(nums[start], nums[i]); temp.push_back(nums[start]); backtrack(result, temp, nums, start + 1); temp.pop_back(); } } }class Solution { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> result = new ArrayList<>(); backtrack(result, new ArrayList<>(), nums, 0); return result; } private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int start) { if (start == nums.length) { result.add(new ArrayList<>(tempList)); } for (int i = start; i < nums.length; i++) { Collections.swap(Arrays.asList(nums), start, i); tempList.add(nums[start]); backtrack(result, tempList, nums, start + 1); tempList.remove(tempList.size() - 1); } } }def permute(nums): result = []; def backtrack(start, end): if start == end: result.append(nums[:]); for i in range(start, end): nums[start], nums[i] = nums[i], nums[start]; backtrack(start + 1, end); nums[start], nums[i] = nums[i], nums[start]; backtrack(0, len(nums)); return resultfunction permute(nums) { let result = []; function backtrack(start, end) { if (start === end) { result.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 result; }Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.