Problem Statement

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

LeetCode:

• https://leetcode.com/problems/permutations/description/

Examples

Example 1:

Input: nums = [1, 2, 3]
Output: [
         [1,2,3],
         [1,3,2],
         [2,1,3],
         [2,3,1],
         [3,1,2],
         [3,2,1]
        ]

Example 2:

Input: nums = [0, 1]
Output: [
         [0, 1],
         [1, 0]
        ]

Example 3:

Input: nums = [1]
Output: [
         [1]
        ]

Different Approaches

1️⃣ Classic Backtracking

Code:

// Helper function for backtracking
void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
    // Base Case: If the current path is a full-length permutation
    if (path.size() == nums.size()) {
        res.push_back(path); // Add a copy of the path to results
        return;
    }

    // Try every unused element at this position
    for (int i = 0; i < nums.size(); ++i) {
        // If nums[i] is already used in the current permutation, skip it
        if (used[i]) continue;

        // Step 1: Choose the element nums[i]
        used[i] = true;
        path.push_back(nums[i]);

        // Step 2: Explore further with nums[i] added to the path
        backtrack(nums, used, path, res);

        // Step 3: Undo the choice (backtrack)
        path.pop_back();       // Remove the last added element
        used[i] = false;       // Mark nums[i] as unused again
    }
}

// Main function to generate all permutations
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;                  // Result to store all permutations
    vector<int> path;                         // Current permutation path
    vector<bool> used(nums.size(), false);    // Tracks whether an element is used
    backtrack(nums, used, path, res);         // Begin backtracking
    return res;
}

Complexity Analysis:

• Time Complexity: O(n! * n)
• Space Complexity: O(n)
  • Space for path, used array, and recursion stack.

2️⃣ In-place Backtracking using Swapping

Code:

// Helper function to generate all permutations using in-place swapping
void backtrack(int idx, vector<int>& nums, vector<vector<int>>& res) {
    // Base case: If the current index reaches the end of the array,
    // we have formed one complete permutation
    if (idx == nums.size()) {
        res.push_back(nums); // Add the current permutation to result
        return;
    }

    // Iterate through all elements starting from 'idx'
    for (int i = idx; i < nums.size(); ++i) {
        // Step 1: Swap the current index with the i-th index
        // This fixes nums[i] at position 'idx'
        swap(nums[idx], nums[i]);

        // Step 2: Recurse for the next index
        backtrack(idx + 1, nums, res);

        // Step 3: Backtrack (undo the swap to restore original state)
        swap(nums[idx], nums[i]);
    }
}

// Main function to initiate the permutation generation
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> res;           // To store all the permutations
    backtrack(0, nums, res);           // Start backtracking from index 0
    return res;                        // Return the final result
}

Complexity Analysis:

• Time Complexity: O(n * n!)
• Space Complexity: O(n)
  • Call stack depth in recursion: O(n)
  • Result space: Holds n! permutations of length n→O(n*n!) (but that's output space, not auxiliary)
  • No use of extra variable path