How to Solve: Permutations (All Unique, With Duplicates) – Complete Guide for FAANG Interviews

How to Solve: Permutations (All Unique, With Duplicates) – Complete Guide for FAANG Interviews

? Introduction

"Permutations appear in 1 out of every 3 onsite interviews—master this, and you’ll prove you can handle recursion, backtracking, and edge cases like a senior engineer."

? WHAT YOU NEED TO KNOW FIRST

Before tackling permutations, ensure you understand: 1. Recursion & Backtracking – Breaking problems into smaller subproblems and undoing choices. 2. Hash Sets / Frequency Maps – Tracking used elements (especially for duplicates). 3. Time Complexity of Recursive Algorithms – How to analyze O(n!) and pruning optimizations.

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow these steps for every permutation problem:

1. Clarify Input Constraints
2. Are elements unique or duplicates allowed?
3. Is the input sorted? (If not, sort first for duplicates.)

4. Are there constraints (e.g., max length, sum conditions)?

5. Choose a Base Approach

6. Unique elements? → Backtracking with swapping or visited array.
7. Duplicates? → Sort + skip duplicates in recursion.

8. Space optimization? → In-place swapping (no extra visited array).

9. Define the Recursive Function

10. Parameters:
    • start (current position in the array).
    • path (current permutation being built).
    • visited (track used indices, if needed).
11. Base Case:
    • If start == len(nums), add path to result.

12. Recursive Case:

    • Loop through candidates (from start to end).
    • Skip duplicates (if applicable).
    • Make a choice (swap or mark as visited).
    • Recurse.
    • Undo the choice (backtrack).

13. Handle Duplicates (If Applicable)

14. Sort the array first.

15. Skip duplicates by checking:
    python
if i > start and nums[i] == nums[i-1]:
continue

16. Optimize for Edge Cases

17. Empty input? → Return [[]].
18. Single element? → Return [[nums[0]]].

19. Large input? → Consider iterative DFS if recursion depth is a concern.

20. Analyze Time & Space Complexity

21. Time: O(n!) (all permutations) or O(n! / (k1! k2! ...)) (with duplicates).

22. Space: O(n) (recursion stack) or O(n!) (if storing all results).

23. Test with Examples

24. Manually walk through small cases (e.g., [1,2,3] and [1,1,2]).
25. Check for missing permutations or duplicates.

? WORKED EXAMPLES

Example 1 – Basic: Permutations of Unique Elements

Problem: Given an array nums with unique elements, return all possible permutations.

Thought Process

1. Input: [1,2,3] → Output: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]].
2. Approach: Backtracking with swapping (in-place, no extra space).
3. Base Case: When start == len(nums), add the current permutation.
4. Recursive Case: Swap nums[i] with nums[start], recurse, then swap back.

Solution Code (Python)

def permute(nums):

    def backtrack(start):

        if start == len(nums):

            result.append(nums.copy())

            return

        for i in range(start, len(nums)):

            nums[start], nums[i] = nums[i], nums[start]  # Swap

            backtrack(start + 1)

            nums[start], nums[i] = nums[i], nums[start]  # Swap back


    result = []

    backtrack(0)

    return result

Complexity

• Time: O(n!) (all permutations).
• Space: O(n) (recursion stack, no extra space for visited).

Why This Works

• Swapping ensures all possible orderings are explored.
• Backtracking undoes swaps to restore the original array for the next iteration.

Example 2 – Medium: Permutations with Duplicates

Problem: Given an array nums with duplicates, return all unique permutations.

Thought Process

1. Input: [1,1,2] → Output: [[1,1,2], [1,2,1], [2,1,1]].
2. Approach: Sort + backtracking with skipping duplicates.
3. Key Insight: Skip duplicates by checking if i > start and nums[i] == nums[i-1].

Solution Code (Python)

def permuteUnique(nums):

    def backtrack(start):

        if start == len(nums):

            result.append(nums.copy())

            return

        for i in range(start, len(nums)):

            if i > start and nums[i] == nums[i-1]:

                continue  # Skip duplicates

            nums[start], nums[i] = nums[i], nums[start]

            backtrack(start + 1)

            nums[start], nums[i] = nums[i], nums[start]


    nums.sort()  # Sort to group duplicates

    result = []

    backtrack(0)

    return result

Complexity

• Time: O(n! / (k1! k2! ...)) (fewer permutations due to duplicates).
• Space: O(n) (recursion stack).

Why This Works

• Sorting groups duplicates together.
• Skipping duplicates ensures no redundant permutations are generated.

Example 3 – Hard/Follow-up: Permutations with Constraints (e.g., Sum)

Problem: Given nums and a target k, return all permutations where the sum of elements equals k.

Thought Process

1. Input: nums = [1,2,3], k = 3 → Output: [[1,2], [2,1], [3]].
2. Approach: Backtracking with pruning (early termination if sum exceeds k).
3. Key Insight: Track the current sum and stop early if it exceeds k.

Solution Code (Python)

def permutationSum(nums, k):

    def backtrack(start, path, current_sum):

        if current_sum == k:

            result.append(path.copy())

            return

        for i in range(len(nums)):

            if used[i] or current_sum + nums[i] > k:

                continue  # Skip used or invalid sums

            used[i] = True

            path.append(nums[i])

            backtrack(i + 1, path, current_sum + nums[i])

            path.pop()

            used[i] = False


    nums.sort()  # Optional: helps with pruning

    result = []

    used = [False]  len(nums)

    backtrack(0, [], 0)

    return result

Complexity

• Time: O(n!) (worst case, but pruning helps).
• Space: O(n) (recursion stack + used array).

Why This Works

• Pruning avoids unnecessary recursive calls when current_sum > k.
• used array ensures no element is reused.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Here’s your 60-second cheat sheet for permutations: 1. Unique elements? Use backtracking with swapping or a visited array. 2. Duplicates? Sort first, then skip duplicates in recursion. 3. Constraints? Prune early (e.g., sum checks). 4. Edge cases? Test empty input, single element, and duplicates. 5. Time complexity? O(n!) for unique, fewer for duplicates. 6. Space? O(n) for recursion stack, O(n!) if storing results.

Walk in confident—you’ve got this!

? Final Notes

• Practice: LeetCode 46 (Unique), 47 (Duplicates), 39 (Combination Sum).
• Follow-ups: Permutations with constraints (e.g., sum, length).
• Whiteboard Tip: Draw the recursion tree to visualize backtracking.

Now go ace that interview! ?