Skip to main content

47. Permutations II

mediumAsked at LinkedIn

Given 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 Alex Chen, 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

Input
nums = [1,1,2]
Output
[[1,1,2],[1,2,1],[2,1,1]]

Example 2

Input
nums = [1,2,3]
Output
[[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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Permutations II and other LinkedIn interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →