Given an array nums containing distinct integers, return all possible permutations. You may return the answer in any order.

Example 1:

<strong>Input:</strong> nums = [1,2,3]
<strong>Output:</strong> [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

<strong>Input:</strong> nums = [0,1]
<strong>Output:</strong> [[0,1],[1,0]]

Example 3:

<strong>Input:</strong> nums = [1]
<strong>Output:</strong> [[1]]

Approach and Algorithm

This problem can be visualized as having a sequence of empty slots where we need to fill each sllot from left to right using numbers from the given array, ensuring that each number is used exactly once. A brute-force approach would involve trying every possible combination until valid permutations are found. In programming practice, this process is efficiently handled using backtracking.

We define a recursive function that fills the i-th position with a current permutation state. The recursion has two scenarios:

• If all positions have been filled (i equals the length of the array), we've found a complete permutation which should be added to our result collection before terminating the recursion.
• Otherwise, for filling position i, we must select among unused elements. Traditionally, one might use a boolean marker array to track used values. However, there's a more space-efficient method: partitioning the input array into two segments—left side storing already placed items and right side holding candidates yet to be positioned. During backtracking, swapping operations maintain this division dynamically.

To illustrate, suppose we're placing the third element out of five availabel ones [2, 5, 8, 9, 10]. If the first two placements were 8 and 9 respectively, then at index 2 we decide to place value 10. By exchanging indices 2 and 4, we ensure proper segregation between fixed and remianing choices. Upon returning from deeper recursions, another swap reverts changes for exploring alternative branches.

Note that while this technique avoids extra memory overhead compared to auxiliary flags, it does not preserve lexicographical ordering within results. For ordered outputs, consider employing traditional tracking mechanisms instead.

Implementation

class Solution {
public:
    void generatePerms(vector<vector<int>>& results, vector<int>& data, int pos, int size) {
        if (pos == size) {
            results.push_back(data);
            return;
        }

        for (int j = pos; j < size; ++j) {
            swap(data[pos], data[j]);
            generatePerms(results, data, pos + 1, size);
            swap(data[pos], data[j]); // backtrack
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        generatePerms(ans, nums, 0, nums.size());
        return ans;
    }
};

Complexity Analysis

• Time Complexity: O(n!), where n represents the number of elements in the input list. Each permutation requires copying the entire arrangement costing O(n). Since total unique arrangements equal factorial of n, overall runtime becomes O(n × n!).
• Space Complexity: O(n), primarily due to call stack depth during recursion reaching up to n levels. Additionally, temporary storage holds intermediate states but doesn't exceed linear proportion relative to input size excluding final output container.