DEV Community

Dev Cookies
Dev Cookies

Posted on

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; } } }
Enter fullscreen mode Exit fullscreen mode

🔹 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]
Enter fullscreen mode Exit fullscreen mode

📌 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]
Enter fullscreen mode Exit fullscreen mode

📌 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; } }
Enter fullscreen mode Exit fullscreen mode

✅ 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; } }
Enter fullscreen mode Exit fullscreen mode

✅ 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--); }
Enter fullscreen mode Exit fullscreen mode

📌 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; } }
Enter fullscreen mode Exit fullscreen mode

🔹 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

Top comments (0)