• The number of permutations is n!, where n is the length of the input list.
Goal: The goal is to generate all possible permutations of the input list of distinct integers.
Steps:
• 1. Use a backtracking approach to explore all permutations of the input list.
• 2. At each step, keep track of elements used and backtrack when a permutation is completed.
• 3. Once a valid permutation is found, store it in the result list.
Goal: The input array contains up to 6 distinct integers. Each integer is within the range of -10 to 10.
Steps:
• The input array length is between 1 and 6.
• The integers in the array are distinct.
Assumptions:
• The integers in the input array are distinct.
• Input: [1, 2, 3]
• Explanation: For the input [1, 2, 3], all possible permutations include [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], and [3, 2, 1].
• Input: [4, 5]
• Explanation: For the input [4, 5], the two possible permutations are [4, 5] and [5, 4].
• Input: [8]
• Explanation: For the input [8], the only possible permutation is [8].
Approach: The solution uses backtracking to generate all possible permutations of the input list. At each step, we explore every element that hasn't been used in the current permutation.
Observations:
• The number of permutations grows factorially with the size of the input list.
• Backtracking is a good approach for generating all possible combinations.
• To generate the permutations, we can use recursion and backtrack once we find a valid permutation.
Steps:
• 1. Create a helper function for backtracking that will explore every possible permutation.
• 2. Track the used elements in each step to avoid repeating numbers in the current permutation.
• 3. Once a valid permutation is formed (i.e., its length matches the input length), add it to the results.
Empty Inputs:
• The input will never be empty because the constraints specify a minimum length of 1.
Large Inputs:
• The maximum input size is 6, so the solution should handle the factorial growth of the number of permutations.
Special Values:
• The elements are distinct, so no duplicates will occur in the input.
Constraints:
• Ensure efficient backtracking, especially as the number of permutations grows with input size.
This line declares a function named `permute` that takes a vector of integers `nums` as input and returns a vector of vectors representing all possible permutations of the input array.
2 : Map Initialization
map<int, bool> mp;
This line initializes a map `mp` to keep track of which numbers have already been used in the current permutation.
3 : Vector Initialization
vector<vector<int>> ans;
This line initializes a 2D vector `ans` to store the resulting permutations.
4 : Vector Initialization
vector<int> tmp;
This line initializes a vector `tmp` to store the current permutation being built.
5 : Backtracking Function Call
bt(ans, tmp, nums, 0, mp);
This line calls the helper function `bt` to perform the backtracking process. The `ans`, `tmp`, `nums`, `0`, and `mp` are passed as arguments.
6 : Return Result
return ans;
This line returns the `ans` vector containing all possible permutations.
7 : Backtracking Function Declaration
voidbt(vector<vector<int>>&ans, vector<int>&tmp, vector<int>&nums, int idx, map<int, bool>&mp) {
This line declares a recursive backtracking function `bt` that takes the following parameters: `ans` to store the result, `tmp` to store the current permutation, `nums` the input array, `idx` to track the current index in the permutation, and `mp` to keep track of used numbers.
8 : Base Case and Result Addition
if(idx == nums.size()) {
This line checks the base case: if the current index `idx` reaches the end of the array, it means a complete permutation has been formed. The current permutation `tmp` is added to the `ans` vector.
9 : Base Case and Result Addition
ans.push_back(tmp);
This line adds the current permutation `tmp` to the `ans` vector.
10 : Base Case and Result Addition
return;
This line returns from the function as a complete permutation has been found.
11 : Loop Iteration
for(int i =0; i < nums.size(); i++) {
This line starts a `for` loop to iterate over each number in the `nums` array.
12 : Skip Used Numbers
if(mp.count(nums[i])) continue;
This line checks if the current number `nums[i]` has already been used in the current permutation. If so, it skips to the next number.
13 : Mark Number as Used
mp[nums[i]] =true;
This line marks the current number `nums[i]` as used in the `mp` map.
14 : Add Number to Current Permutation
tmp.push_back(nums[i]);
This line adds the current number `nums[i]` to the current permutation `tmp`.
15 : Recursive Call
bt(ans, tmp, nums, idx +1, mp);
This line recursively calls the `bt` function with the updated `idx` to explore the next position in the permutation.
16 : Backtrack
tmp.pop_back();
This line removes the last added number from the `tmp` permutation to backtrack to the previous state.
17 : Mark Number as Unused
mp.erase(nums[i]);
This line removes the current number `nums[i]` from the `mp` map, indicating that it can be used again in other permutations.
Best Case: O(n!)
Average Case: O(n!)
Worst Case: O(n!)
Description: The time complexity is O(n!) due to the need to generate all possible permutations of n elements.
Best Case: O(n!)
Worst Case: O(n!)
Description: The space complexity is O(n!) due to the storage of all permutations and the recursive stack.
