Katkat
Back

Generate unique permutations with duplicates

MetaMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates a candidate's understanding of permutation generation and duplicate handling within algorithm design, testing combinatorial reasoning, correctness proofs, and time/space complexity analysis.

Given an array of integers that may contain duplicates, generate all unique permutations. Ensure no duplicate permutations are returned even if some values occur more than twice. Describe your algorithm (e.g., backtracking with frequency counts), prove correctness, and analyze time and space complexity.