LeetCode 47 Explained 🔁 | Unique Permutations Using In-Place Backtracking (Java)

🚀 Problem Overview

In LeetCode 47 (Permutations II), we’re asked to generate all unique permutations of an array that may contain duplicate elements.
The challenge is avoiding repeated permutations without using extra global data structures to filter results afterward.

🧠 Algorithm & Approach (What This Video Covers)

In this video, I walk through an efficient in-place backtracking solution using swapping + a HashSet at each recursion level.

✅ Key Ideas:
We generate permutations by fixing one index at a time
At each recursion depth, we use a HashSet to ensure:
Each number is used only once per position
Duplicate permutations are avoided early (pruning)
We swap elements in-place, reducing memory usage
After recursion, we backtrack by undoing the swap

🔁 Why This Works:
Duplicate numbers cause repeated permutations
The HashSet ensures we don’t swap the same value into the same index more than once
This guarantees only unique permutations are produced

⏱️ Complexity Analysis

Time Complexity:
O(n!×n) — generating permutations + converting arrays to lists

Space Complexity:
O(n) — recursion stack + HashSet per level (excluding output)

💡 Why This Solution Is Powerful
No sorting required
No global Set
Clean, readable, and interview-ready
Shows strong understanding of backtracking with pruning

📌 What You’ll Learn
How to handle duplicates in permutation problems
In-place backtracking techniques
Smart pruning using HashSet
Writing clean recursive solutions in Java

👍 Like, comment, and subscribe if this helped you
💬 Questions and improvements are always welcome

Follow me on my socials to connect and see more awesome stuff

📌 *GitHub:* [https://github.com/NganeEmmanue](https://github.com/NganeEmmanue)
💼 *LinkedIn:* [  / ngane-emmanuel-b25242150  ](  / ngane-emmanuel-b25242150  )
📸 *Instagram:* @nganeemmanuel