Red-Green-Code

Deliberate practice techniques for software developers

  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter

LeetCode 47: Permutations II

By Duncan Smith Feb 17 0

LeetCode 2021

Problem

LeetCode 47: Permutations II (Medium)

Problem Statement: Given a list of integers that may contain duplicates, return all possible unique permutations of those integers, in any order.

A permutation is an arrangement of elements. For example, the three elements [1,2,3] can be arranged into $3!=6$ unique permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1]. For this problem, the input list can have duplicate elements (that’s the extra requirement compared to the previous problem, LeetCode 46: Permutations), but the answer must not have any duplicate permutations.

Solution

The canonical algorithm for finding permutations is recursive backtracking, so we’ll take that approach.

Pseudocode

The solution uses two functions: the main function, which sets up the recursion and returns the result, and the recursive backtracking function.

The main function accepts a list of integers. The first step is to sort this input array. This is a simple way to avoid duplicate permutations. Then we call the recursive function and return the result. The 0 argument in the backtrack call means start the process at position 0 in nums (the input list).

sort the input list (nums)
backtrack(nums, 0)
return result

In the backtrack function, we’ll need four variables, the first three of which are passed as parameters:

  • result: The list of permutations
  • nums: One unique permutation of the input list
  • i: The starting position in the current permutation
  • j: The current position in the current permutation

For the recursive base case, we check if our starting position is past the end of the current permutation. If it is, the current permutation is done, so we can add it to our list of results, and return:

if i is past the end of the current permutation
    add the current permutation to the result
    return

Now the real work begins. We’ll use a combination of iteration and recursion. The iteration loop on j goes from i (the starting position) to the end of the current permutation, nums. For each j (the current position), we’ll check the values at nums[i] and nums[j]. If they’re different, we swap them and recursively start the process again at the next starting position i+1. As a special case, we also make the recursive call when i==j. To keep the code simple, we also do the swap in this case, though it has no effect since we’re swapping an element with itself.

for each j from i to end of nums
    if nums[i] and nums[j] are different or i==j
        swap nums[i] and nums[j]
        backtrack(copy of nums, i+1)

One implementation detail: When we make the recursive call, we need to send a copy of nums, not just a reference to nums. This is how we generate new permutations. If we sent a reference, we would overwrite the result of previous swaps.

Why does this process work? Since permutations are arrangements of the input values, it makes sense that we could generate these arrangements by swapping. The key is to make sure we use all possible swap positions (except where the swap would have no effect because the source and destination elements are the same). Notice that i covers every position in nums from 0 to the last element. And j covers every position from i to the last element. So (ignoring duplicates), we swap position 0 with positions 0, 1, …, n-1, position 1 with 1, 2, …, n-1, and so on until i==n. So it seems reasonable that this would cover every possible swap.

As with last week’s recursive problem, instrumentation can help illuminate the flow of control in a recursive algorithm. Here’s what happens when the input is 1,1,2. Note that some swaps are skipped in this example, since the input contains a duplicate 1 element:

i=0, j=0
1 1 2 
i=1, j=1
1 1 2 
i=2, j=2
1 1 2 
i=3, adding to result:
--> 1 1 2 
Returned from backtrack at i=2, j=2
Returned from backtrack at i=1, j=1
i=1, j=2
1 2 1 
i=2, j=2
1 2 1 
i=3, adding to result:
--> 1 2 1 
Returned from backtrack at i=2, j=2
Returned from backtrack at i=1, j=2
Returned from backtrack at i=0, j=0
i=0, j=2
2 1 1 
i=1, j=1
2 1 1 
i=2, j=2
2 1 1 
i=3, adding to result:
--> 2 1 1 
Returned from backtrack at i=2, j=2
Returned from backtrack at i=1, j=1
Returned from backtrack at i=0, j=2

Code

Permutations II on GitHub

LeetCode Model Solutions

I’m posting some LeetCode model solutions this year. For more about this, see A Project for 2021.

Categories: LeetCode

Prev
Next

Stay in the Know

I'm trying out the latest learning techniques on software development concepts, and writing about what works best. Sound interesting? Subscribe to my free newsletter to keep up to date. Learn More
Unsubscribing is easy, and I'll keep your email address private.

Getting Started

Are you new here? Check out my review posts for a tour of the archives:

  • Lessons from the 2020 LeetCode Monthly Challenges
  • 2019 in Review
  • Competitive Programming Frequently Asked Questions: 2018 In Review
  • What I Learned Working On Time Tortoise in 2017
  • 2016 in Review
  • 2015 in Review
  • 2015 Summer Review

Archives

Recent Posts

  • Quora: How to Read Cracking the Coding Interview April 21, 2021
  • Quora: What to Do When You’re Stuck on a Competitive Programming Problem April 14, 2021
  • Quora: How to Get Better at Competitive Programming April 7, 2021
  • Quora: Is LeetCode Useful for Beginning Competitive Programmers? March 31, 2021
  • How to LeetCode March 24, 2021
  • LeetCode 322: Coin Change March 17, 2021
  • LeetCode 152: Maximum Product Subarray March 10, 2021
  • LeetCode 856: Score of Parentheses March 3, 2021
  • LeetCode 11: Container With Most Water February 24, 2021
  • LeetCode 47: Permutations II February 17, 2021
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2021 Duncan Smith