Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Permutations (medium)

Problem Statement

Given a set of distinct numbers, find all of its permutations.

Permutation is defined as the re-arranging of the elements of the set. For example, {1, 2, 3} has the following six permutations:

{1, 2, 3} {1, 3, 2} {2, 1, 3} {2, 3, 1} {3, 1, 2} {3, 2, 1}

If a set has n distinct elements it will have n! permutations.

Example 1:

Input: [1,3,5]
Output: [1,3,5], [1,5,3], [3,1,5], [3,5,1], [5,1,3], [5,3,1]

Constraints:

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • All the numbers of nums are unique.

.....

.....

.....

Like the course? Get enrolled and start learning!
K

k

· 3 years ago

"If a set has ‘n’ distinct elements it will have n!n! permutations.". It should be n! only.

A

andrew rivada

· 4 years ago

How do you solve this if the numbers are not distinct?

Show 4 replies
N

Nuttapong Saelek

· 3 years ago

Contradictory between the code and the description, the description says "we are iterating through all of these permutations with the help of the two ‘for’ loops". Apparently, from the code, we make 3 loops.

Should the time complexity be O(N^2*N!) instead?

Show 1 reply
Andrii Y

Andrii Y

· 2 years ago

Description says:

Given a set of distinct numbers, find all of its permutations.

However, one of the test cases contains duplicate numbers: [1, 3, 5]

[1, 2]

[2, 2]

Show 1 reply
L

lejafilip

· 2 years ago

You are inserting elements into vector which means that you have to reallocate whole vector and you repeat it several times. I know that it isn't about language but ... I found that c++ level in this course is really bad. Sorry but I have to say it ...

J

Jacques

· 4 years ago

what is the advantage of deque here in js solution? I did the same general thing but kept my result as an array of arrays that was replaced each time i finished adding an element to each. function test(distinct) { let output = [[]]; distinct.forEach(el => { const newOutput = [] output.forEach(ar => { const possiblePlaces = ar.length + 1 for (let i = 0; i < possiblePlaces; i++) { const newArr = [] for (let j = 0; j < i; j++) { newArr.push(ar[j]) } newArr.push(el) for (let j = i; j < ar.length; j++) { newArr.push(ar[j]) } newOutput.push(newArr) } }) output = newOutput }) return output }

Show 2 replies
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

from collections import deque

class Solution:
  def findPermutations(self, nums):
  
    def backtrack(index, result, path, seen):
      if len(path) == len(nums):
        result.append(path[:])
        return 

      for i, num in enumerate(nums):
        if i not in seen:
          seen.add(i)
          path.append(num)
          backtrack(i, result, path, seen)
          seen.remove(i)
          path.pop()
    
    result = []
    backtrack(0, result, [], set())

    return result
Debasis B

Debasis B

· a year ago

 // List to store all permutations
 List<List<int>> result = new List<List<int>>();

 public List<List<int>> findPermutations(int[] nums)
 {
     // Start the recursive permutation finding process
     findPermutations(nums, currIndex: 0, currPermutation: new List<int>());
     return result;
 }

 private void findPermutations(int[] nums, int currIndex, List<int> currPermutation)
 {
     // Base case: if the current index is beyond the last index, add the permutation to the result
     if (currIndex > nums.Length - 1)
     {
         result.Add(new List<int>(currPermutation));
         return;
     }

     // Insert the current element at all possible positions in the current permutation
     for (int i = 0; i < currIndex + 1; i++)
     {
         currPermutation.Insert(i, nums[cu