Permutations II - Practice Coding Problems

Permutations II - Problem

Given a collection of numbers nums that might contain duplicates, return all possible unique permutations in any order.

A permutation is a rearrangement of elements where order matters. Since the input may contain duplicate numbers, we need to ensure that our result contains only unique permutations (no duplicate permutations in the output).

Key Challenge: Handle duplicate elements properly to avoid generating duplicate permutations.

Input & Output

Example 1 — With Duplicates

$ Input: nums = [1,1,2]

› Output: [[1,1,2],[1,2,1],[2,1,1]]

💡 Note: The input has duplicate 1s. All unique permutations are: [1,1,2], [1,2,1], and [2,1,1]. Note that [1,1,2] appears only once in output despite having two 1s.

Example 2 — All Duplicates

$ Input: nums = [1,2,1,1]

› Output: [[1,1,1,2],[1,1,2,1],[1,2,1,1],[2,1,1,1]]

💡 Note: Three 1s and one 2. The unique permutations arrange the three 1s in different positions with the single 2.

Example 3 — No Duplicates

$ Input: nums = [1,2,3]

› Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

💡 Note: No duplicate elements, so we get all 3! = 6 possible permutations of the three distinct numbers.

Constraints

1 ≤ nums.length ≤ 8
-10 ≤ nums[i] ≤ 10

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,1,2] with duplicate elements

Process

Generate all unique arrangements

Output

3 unique permutations: [[1,1,2],[1,2,1],[2,1,1]]

Key Takeaway

🎯 Key Insight: Sort first, then skip duplicates at the same recursion level to avoid generating duplicate permutations

Asked in

M Microsoft 35 a Amazon 28 G Google 25 A Apple 22

The key insight is to sort the input array first, then use backtracking while skipping duplicate elements at the same recursion level. This prevents generating duplicate permutations. Best approach is optimized backtracking. Time: O(n! × n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Backtracking with Pruning	O(n! × n)	O(n)	Sort first, then skip duplicates at same level
Brute Force with Set Deduplication	O(n! × n)	O(n! × n)	Generate all permutations, use set to remove duplicates

Optimized Backtracking with Pruning — Algorithm Steps

Sort the input array to group duplicates together
Use backtracking with a used array to track elements
Skip duplicate elements at the same recursion level

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort Input

Group duplicate elements together

Backtrack

Skip duplicates at same recursion level

Result

Only unique permutations generated

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_SIZE 8
#define MAX_RESULTS 40320

int results[MAX_RESULTS][MAX_SIZE];
int resultSizes[MAX_RESULTS];
int resultCount = 0;

int compare(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

void backtrack(int* nums, int numsSize, int* path, int pathSize, int* used) {
    if (pathSize == numsSize) {
        for (int i = 0; i < pathSize; i++) {
            results[resultCount][i] = path[i];
        }
        resultSizes[resultCount] = pathSize;
        resultCount++;
        return;
    }
    
    for (int i = 0; i < numsSize; i++) {
        if (used[i]) continue;
        // Skip duplicates at same level
        if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
        
        used[i] = 1;
        path[pathSize] = nums[i];
        backtrack(nums, numsSize, path, pathSize + 1, used);
        used[i] = 0;
    }
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[MAX_SIZE];
    int size = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL && size < MAX_SIZE) {
        nums[size++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    qsort(nums, size, sizeof(int), compare);  // Sort to group duplicates
    
    int path[MAX_SIZE];
    int used[MAX_SIZE] = {0};
    backtrack(nums, size, path, 0, used);
    
    printf("[");
    for (int i = 0; i < resultCount; i++) {
        printf("[");
        for (int j = 0; j < resultSizes[i]; j++) {
            printf("%d", results[i][j]);
            if (j < resultSizes[i] - 1) printf(",");
        }
        printf("]");
        if (i < resultCount - 1) printf(",");
    }
    printf("]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n! × n)

In worst case (no duplicates), we generate n! permutations, each taking O(n) to build

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion depth is n, plus used array of size n

⚡ Linearithmic Space

216.0K Views

Medium Frequency

~25 min Avg. Time

7.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Backtracking with Pruning — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler