47. Permutations II
mediumAsked at LinkedInGiven a collection of integers (possibly with duplicates), return all unique permutations. LinkedIn asks this on the backtracking round — they want the sort-then-skip-duplicates pattern, not generate-then-dedupe.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in LinkedIn loops.
- Glassdoor (2026-Q1)— LinkedIn SWE onsite reports list Permutations II as the backtracking problem when the loop wants a duplicate-handling twist.
- Blind (2025-12)— LinkedIn writeups specifically cite the 'skip identical at same depth' trick as the signal.
Problem
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
Constraints
1 <= nums.length <= 8-10 <= nums[i] <= 10
Examples
Example 1
nums = [1,1,2][[1,1,2],[1,2,1],[2,1,1]]Example 2
nums = [1,2,3][[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]Approaches
1. Generate all then dedupe
Use the standard Permutations I backtracking, dedupe with a Set on stringified tuples.
- Time
- O(n * n!) with extra dedup overhead
- Space
- O(n * n!) for the Set
function permuteUniqueDedup(nums) {
const out = new Set();
const used = new Array(nums.length).fill(false);
function bt(path) {
if (path.length === nums.length) { out.add(path.join(',')); return; }
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
used[i] = true;
path.push(nums[i]);
bt(path);
path.pop();
used[i] = false;
}
}
bt([]);
return [...out].map(s => s.split(',').map(Number));
}Tradeoff: Correct but wastes work generating duplicates first. The Set adds O(n) per insertion. Useful only as the contrast for the skip-duplicates version.
2. Sort + skip-duplicates-at-same-depth (optimal)
Sort first. In the backtracking loop, if nums[i] === nums[i-1] AND nums[i-1] is unused at the current depth, skip nums[i] — its permutations are already covered by the earlier copy.
- Time
- O(n * n!) but with early pruning
- Space
- O(n) recursion
function permuteUnique(nums) {
nums.sort((a, b) => a - b);
const out = [];
const used = new Array(nums.length).fill(false);
function bt(path) {
if (path.length === nums.length) { out.push(path.slice()); return; }
for (let i = 0; i < nums.length; i++) {
if (used[i]) continue;
if (i > 0 && nums[i] === nums[i - 1] && !used[i - 1]) continue;
used[i] = true;
path.push(nums[i]);
bt(path);
path.pop();
used[i] = false;
}
}
bt([]);
return out;
}Tradeoff: Same asymptotic complexity but no wasted work — duplicates are skipped before recursion. The `!used[i-1]` check is the critical line: it skips THIS copy of the duplicate only when the earlier copy hasn't been used at the current depth.
LinkedIn-specific tips
LinkedIn interviewers specifically want the `!used[i-1]` justification. Articulate: 'If the previous duplicate is unused at this depth, picking this one now creates the SAME tree as if I had picked the previous one — I'd be generating duplicate permutations.' That sentence carries the entire skip rule. Many candidates write `used[i-1]` (without the `!`) which is the wrong direction and silently generates duplicates anyway.
Common mistakes
- Writing `used[i-1]` instead of `!used[i-1]` — the direction matters; one generates duplicates, the other skips them.
- Forgetting to sort first — the skip-condition relies on identical values being adjacent.
- Using a Set + stringify when sorting + skip is faster and cleaner.
Follow-up questions
An interviewer at LinkedIn may pivot to one of these next:
- Permutations (LC 46) — no duplicates, no skip rule needed.
- Next Permutation (LC 31) — lexicographic next.
- Combinations (LC 77) — sibling problem with the same skip pattern for duplicates.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why does the skip rule use `!used[i-1]` and not `used[i-1]`?
Because if the previous copy IS used (in the current path), picking this copy as the next element gives a NEW permutation — same numbers but at different positions. If the previous copy ISN'T used at this depth, picking this copy would mirror the tree the previous copy would have rooted — a duplicate.
Could this be done with a swap-based recursion?
Yes — swap nums[start] with each j in [start, n), recurse on start+1. Dedup by skipping nums[j] if it's already appeared in [start, j) (using a Set per recursion call). Slightly more memory but no sort dependency.
Free learning resources
Curated free links for this problem.