Blog 3: Permutation Pattern (Extended Guide)

🔹 Introduction

The permutation pattern is one of the most classic backtracking applications. It is used in:

• Arrangements (e.g., seating, task ordering).
• String anagrams.
• Puzzle solving (like word rearrangements).
• Combinatorial enumeration.

👉 Interviewers love this pattern because it tests recursion, backtracking, and handling duplicates.

---

🔹 Core Idea

At each step:

1. Choose an unused element.
2. Add it to the current sequence.
3. Recurse to place the next element.
4. Undo (backtrack).

---

🔹 Base Template (All Permutations)

import java.util.*;

public class PermutationPattern {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(new ArrayList<>(), used, nums, results);
        return results;
    }

    private void backtrack(List<Integer> current, boolean[] used, int[] nums, List<List<Integer>> results) {
        if (current.size() == nums.length) {
            results.add(new ArrayList<>(current));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) continue;

            // Choose
            current.add(nums[i]);
            used[i] = true;

            // Explore
            backtrack(current, used, nums, results);

            // Undo (Backtrack)
            current.remove(current.size() - 1);
            used[i] = false;
        }
    }
}

---

🔹 Recursion Tree (for [1,2,3])

            []
   /          |         \
 [1]         [2]        [3]
 / \         / \        / \
[1,2][1,3] [2,1][2,3] [3,1][3,2]
  |     |    |     |    |     |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

📌 Each leaf = one valid permutation.

---

🔹 Variations of Permutations

Now let’s cover all interview-relevant variations.

---

✅ 1. Permutations of an Array of Distinct Integers

• Input: [1,2,3]
• Output: All 6 permutations.

👉 Already covered with base template.

---

✅ 2. Permutations with Duplicates (Avoid Duplicates)

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

[1,1,2]
[1,2,1]
[2,1,1]

📌 Trick: Sort array + skip duplicates if previous is not used.

public List<List<Integer>> permuteUnique(int[] nums) {
    Arrays.sort(nums); // sort to handle duplicates
    List<List<Integer>> results = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrackDup(new ArrayList<>(), used, nums, results);
    return results;
}

private void backtrackDup(List<Integer> current, boolean[] used, int[] nums, List<List<Integer>> results) {
    if (current.size() == nums.length) {
        results.add(new ArrayList<>(current));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; // skip duplicate

        current.add(nums[i]);
        used[i] = true;

        backtrackDup(current, used, nums, results);

        current.remove(current.size() - 1);
        used[i] = false;
    }
}

---

✅ 3. String Permutations (All Anagrams)

• Input: "abc"
• Output: "abc", "acb", "bac", "bca", "cab", "cba"

public List<String> permuteString(String s) {
    List<String> results = new ArrayList<>();
    boolean[] used = new boolean[s.length()];
    backtrack(new StringBuilder(), used, s.toCharArray(), results);
    return results;
}

private void backtrack(StringBuilder current, boolean[] used, char[] chars, List<String> results) {
    if (current.length() == chars.length) {
        results.add(current.toString());
        return;
    }

    for (int i = 0; i < chars.length; i++) {
        if (used[i]) continue;

        current.append(chars[i]);
        used[i] = true;

        backtrack(current, used, chars, results);

        current.deleteCharAt(current.length() - 1);
        used[i] = false;
    }
}

---

✅ 4. String Permutations with Duplicates (Unique Anagrams)

• Input: "aab"
• Output: "aab", "aba", "baa"

(Same duplicate handling logic as arrays — sort + skip duplicates.)

---

✅ 5. Next Lexicographical Permutation (LeetCode #31)

Instead of generating all, return the next greater permutation.

public void nextPermutation(int[] nums) {
    int i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) i--;

    if (i >= 0) {
        int j = nums.length - 1;
        while (nums[j] <= nums[i]) j--;
        swap(nums, i, j);
    }
    reverse(nums, i + 1, nums.length - 1);
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

private void reverse(int[] nums, int i, int j) {
    while (i < j) swap(nums, i++, j--);
}

📌 Commonly asked in Google & Amazon interviews.

---

✅ 6. k-Permutations (Partial Permutations)

• Input: [1,2,3], k=2
• Output: [1,2], [1,3], [2,1], [2,3], [3,1], [3,2]

private void backtrackK(List<Integer> current, boolean[] used, int[] nums, int k, List<List<Integer>> results) {
    if (current.size() == k) {
        results.add(new ArrayList<>(current));
        return;
    }

    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;

        current.add(nums[i]);
        used[i] = true;

        backtrackK(current, used, nums, k, results);

        current.remove(current.size() - 1);
        used[i] = false;
    }
}

---

🔹 Complexity Analysis

• Time: O(n! * n) (since we generate n! permutations, each copied in O(n)).
• Space: O(n) recursion + O(n) used array.

---

🔹 Interview References

• LeetCode #46 – Permutations
• LeetCode #47 – Permutations II (duplicates)
• LeetCode #31 – Next Permutation
• Asked in Google, Amazon, Facebook, Microsoft, Uber

---

🔹 Key Takeaways

✅ Subsets → include/exclude choices
✅ Permutations → arrange all elements once
✅ Duplicates → sort + skip
✅ Strings & arrays → same logic
✅ Always remember: n! growth → heavy recursion

---

🔹 What’s Next?

In Blog 4: Combination & Combinatorial Search, we’ll cover:

• k-Combinations (choose k out of n)
• Combination Sum I, II, III
• Letter Case Permutations
• Palindrome Partitioning