Permutations II

TIP103 Unit 8 Session 2 (Click for link to problem statements)

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 25-35 mins
• 🛠️ Topics: Recursion, Backtracking, Permutations, Sorting

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: How is this different from generating all permutations of a list?

  • A: The input may contain duplicate values, so swapping two equal "plus-ones" produces an ordering that looks identical. Each distinct ordering should appear exactly once in the result.

• Q: Does the order of the returned permutations matter?

  • A: No. The permutations may be returned in any order, as long as each unique permutation appears exactly once.

• Q: Can we return fewer than n! permutations?

  • A: Yes. With duplicates, the number of unique permutations is n! divided by the factorial of each value's count, so it is usually smaller than n!.

HAPPY CASE
Input: nums = [1, 1, 2]
Output: [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
Explanation: The two 1s are interchangeable, so only 3 of the 3! = 6 orderings are unique.

Input: nums = [1, 2, 3]
Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Explanation: With no duplicates, all 3! = 6 permutations are unique.

EDGE CASE
Input: nums = [1]
Output: [[1]]
Explanation: A single guest has only one seating.

Input: nums = [2, 2, 2]
Output: [[2, 2, 2]]
Explanation: Every guest is interchangeable, so all 3! orderings collapse into one unique permutation.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Generating Combinations/Permutations Problems, we can consider the following approaches:

• Backtracking (Recursion): Build each permutation one element at a time, undoing choices as we return, which explores every ordering exactly once.
• Sorting + Pruning for Duplicates: Sort the input so equal values sit next to each other, then skip a value when it would repeat the choice its identical neighbor already made at the same position.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Sort nums so duplicates are adjacent. Use backtracking to place one number at a time into a growing permutation, tracking which indices are already used. To avoid duplicate permutations, at each position only allow the first unused copy of a value to be placed: if nums[i] equals nums[i-1] and index i-1 is still unused, skip index i.

1) Sort `nums` so equal values are adjacent.
2) Initialize `results`, an empty `permutation`, and a `used` list of booleans.
3) Define a backtracking helper:
   a) Base case: if `permutation` has all the numbers, append a copy to `results` and return.
   b) For each index `i` in `nums`:
      i)   Skip if `used[i]` is True.
      ii)  Skip if `nums[i] == nums[i-1]` and `used[i-1]` is False (a duplicate would repeat work).
      iii) Mark index `i` used, append `nums[i]`, and recurse.
      iv)  Undo: pop `nums[i]` and mark index `i` unused.
4) Call the helper and return `results`.

⚠️ Common Mistakes

• Forgetting to sort first — the duplicate-skipping check only works when equal values are adjacent.
• Appending the permutation list itself instead of a copy, so every entry in results mutates into the same (empty) list.
• Deduplicating with a set of results at the end instead of pruning — it produces correct output but still does n! work.
• Tracking used by value instead of by index, which wrongly blocks placing a second copy of a duplicate value.

4: I-mplement

Implement the code to solve the algorithm.

def permute_unique(nums):
    nums = sorted(nums)  # Sort so duplicate values sit next to each other
    results = []
    permutation = []
    used = [False] * len(nums)

    def backtrack():
        # Base case: the permutation is complete
        if len(permutation) == len(nums):
            results.append(permutation[:])  # Append a copy
            return
        for i in range(len(nums)):
            # Skip numbers already placed in the current permutation
            if used[i]:
                continue
            # Skip duplicates: only place the first unused copy of a value
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            permutation.append(nums[i])
            backtrack()
            permutation.pop()
            used[i] = False

    backtrack()
    return results

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: nums = [1, 1, 2] (already sorted)

  • Place index 0 (1), then index 1 (1), then index 2 (2) → record [1, 1, 2].
  • Backtrack to [1]; place index 2 (2), then index 1 (1) → record [1, 2, 1].
  • Backtrack to []; index 1 is skipped because nums[1] == nums[0] and index 0 is unused.
  • Place index 2 (2), then index 0 (1), then index 1 (1) → record [2, 1, 1].
  • Output: 1, 1, 2], [1, 2, 1], [2, 1, 1 — matches the expected output, with no duplicates.

• Input: nums = [2, 2, 2]

  • Only index 0 is ever allowed first, then index 1, then index 2.
  • Output: 2, 2, 2 (all other orderings are pruned as duplicates.)

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of elements in nums.

• Time Complexity: O(N * N!) in the worst case (all values distinct): there are up to N! unique permutations, and each takes O(N) work to build and copy. Duplicate pruning makes it faster when values repeat.
• Space Complexity: O(N) auxiliary space for the recursion stack, the used list, and the in-progress permutation (excluding the output list, which holds up to N! permutations of length N).