13.PermutaionsOfAString.md

🔁 Permutations #46

📘 Problem Statement

Given a vector nums of n distinct integers, generate all possible permutations (arrangements) of the elements of nums. Return a vector<vector<int>> containing all permutations in any order.

Constraints (typical):

• 1 <= n <= 8 (factorial growth)
• All elements are distinct (simplifies implementation)

---

🧠 Intuition (What's happening)

There are two common, easy-to-understand approaches:

1. Backtracking with visited/frequency array Build a temporary array ds (current permutation) by choosing one unused element at a time. Use a boolean freq[] to mark which indices are already used. Recurse until permutation length equals n, then record a copy.

2. In-place swapping (generate permutations by swapping) Fix a position ind and try each candidate element to occupy that position by swapping it into ind. Recurse with ind+1. After recursion, swap back (backtrack). This avoids extra freq[] arrays and can be more memory-efficient because it builds permutations in-place.

Both produce the same set of permutations (order may differ) and are standard backtracking patterns.

🐢 Brute Force (conceptually)

A brute force idea would be: for every possible ordering of indices, create a permutation and check uniqueness. Practically this is the same as generating all n! permutations — there is no better lower bound than Ω(n!) because you must output n! permutations. So both backtracking methods are essentially optimal in asymptotic terms for this output size.

---

✅ Clean Code (two approaches)

1) Backtracking with used (visited) array

// Approach 1: Backtracking with visited/frequency array
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> ds;
        vector<bool> used(nums.size(), false);
        backtrack(nums, used, ds, res);
        return res;
    }

private:
    void backtrack(const vector<int> &nums, vector<bool> &used,
                   vector<int> &ds, vector<vector<int>> &res) {
        if (ds.size() == nums.size()) {
            res.push_back(ds); // record a copy
            return;
        }
        for (size_t i = 0; i < nums.size(); ++i) {
            if (used[i]) continue;
            used[i] = true;
            ds.push_back(nums[i]);
            backtrack(nums, used, ds, res);
            ds.pop_back();
            used[i] = false;
        }
    }
};

---

2) In-place swapping (index-based)

// Approach 2: In-place swapping
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        permuteInPlace(0, nums, res);
        return res;
    }

private:
    void permuteInPlace(int ind, vector<int> &nums, vector<vector<int>> &res) {
        if (ind == (int)nums.size()) {
            res.push_back(nums); // push current ordering
            return;
        }
        for (int i = ind; i < (int)nums.size(); ++i) {
            swap(nums[i], nums[ind]);
            permuteInPlace(ind + 1, nums, res);
            swap(nums[i], nums[ind]); // backtrack
        }
    }
};

---

🔍 Why both are correct

• Backtracking with used: At each recursion, you choose any unused element and append it. You explore all n! possible sequences because you try every candidate at every depth.
• In-place swapping: Fixes one position at a time. For index ind, swapping each candidate into ind ensures all permutations with that prefix will be generated. After recursion you restore the array (swap back), so other orderings can be made.

They are standard textbook algorithms.

⏱ Complexity Analysis

Let n = nums.size().

• Number of permutations: n!

• Time Complexity:

  • Both algorithms must generate n! permutations, each of length n to be copied to result → O(n * n!).
  • Overhead of recursion and swaps doesn't change the factorial factor. So time: O(n * n!).

• Space Complexity:

  • Output storage: O(n * n!) (to store all permutations).

  • Additional recursion stack:

    • Backtracking with used: O(n) for ds + O(n) for used + recursion depth O(n) → O(n).
    • In-place swapping: O(n) recursion depth and O(1) extra besides recursion → O(n).

  • So additional aux space (excluding output) is O(n).

---

🧪 Test Cases

1. Small / distinct

   • Input: [1] → Output: [[1]]
   • Input: [1,2] → Output: [[1,2],[2,1]]

2. Three elements

   • Input: [1,2,3] → 6 permutations (all unique)

3. Negative / arbitrary

   • Input: [-1, 0, 1] → works the same

4. Larger n

   • Input: n = 8 (max typical) → 40320 permutations — ensure you have memory/time to handle that.

5. Edge: empty input (if allowed)

   • Input: [] → By convention, permutations of empty set is [[]] (one permutation with zero elements). Current code: if nums.size() == 0:

     • Backtracking version: will push an empty ds once → res = { { } } — correct.
     • In-place version: ind == nums.size() is true at start, so it pushes nums (empty) once → correct.

💡 Tips & Tricks

• Use vector<int> ds; ds.reserve(nums.size()); to avoid repeated reallocations in the backtracking approach.

• For lexicographic order of permutations, you can:

  • Sort nums first and for the in-place approach iterate with next_permutation from STL as an alternative.

• If nums can have duplicates, these algorithms produce duplicate permutations. To handle duplicates:

  • For backtracking with used, sort nums and skip duplicates with an extra check: if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
  • For in-place swapping, use a set or only swap distinct values for a given ind (slightly more complex).

• Use iterative STL approach: start with sorted nums and call std::next_permutation in a loop — easy and sometimes faster in practice.

🔁 Variations

• Permutations II (with duplicates) — produce unique permutations when input has repeated elements. Techniques: sort + skip duplicates.
• k-permutations — generate permutations of length k (choose k elements and permute). Modify depth/stop condition.
• Permutation ranking / unranking — convert between permutation and its lexicographic rank (combinatorial math).
• Generate permutations in lexicographic order — start sorted and use next_permutation.

❗ Common Pitfalls / Bugs

• Forgetting to backtrack (undo changes): e.g., not marking used[i] = false on returning or not swapping back.
• Using nums.size() in loop headers and using int/size_t inconsistently — cast to int if indexes are int.
• If elements are not distinct and you don't handle duplicates, you'll produce repeated permutations.
• Pushing references instead of copies (not an issue here — vector copies contents into res).

🙋 Frequently Asked Questions (FAQ)

Q: Which approach is faster?

A: They are similar asymptotically. The in-place swap approach often has slightly lower constant memory overhead because it avoids an extra ds/used arrays; it constructs permutations in the original array and copies on each leaf. For small n both are fine.

Q: Can we avoid copying the whole permutation when pushing to res?

A: Not if you must retain all permutations. You must store n! vectors each of length n: copying is necessary to preserve each permutation's state. You can, however, move (std::move) if you can reuse buffers, but standard practice is to copy.

Q: Which is easier to modify for duplicates?

A: The backtracking-with-used approach is easier to extend to handle duplicates using the if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; trick after sorting.

Q: What about iterative generation?

A: You can sort nums and call do { res.push_back(nums); } while (next_permutation(nums.begin(), nums.end())); — simple and robust (requires starting sorted to get all permutations).