How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Generate all subsets (handle duplicates)

Q: Generate all subsets (handle duplicates)

This question evaluates understanding of power-set generation and handling of duplicate elements, measuring competency in combinatorics, enumeration techniques and algorithmic problem-solving.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## Problem Given an integer array `nums`, return **all possible subsets** (the power set). ### Part A (no duplicates) Assume all elements in `nums` are **distinct**. Return all subsets in any order. ### Part B (follow-up: may contain duplicates) Now assume `nums` **may contain duplicate values**. Return all **unique** subsets (no duplicate subsets). Subsets can be returned in any order. ## Input - `nums`: an array of integers, length `n` ## Output - A list of lists, where each inner list is a subset of `nums` ## Constraints - `0 <= n <= 20` - `-10 <= nums[i] <= 10` ## Examples ### Example 1 (Part A) Input: `nums = [1,2,3]` Output (one valid ordering): `[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]` ### Example 2 (Part B) Input: `nums = [1,2,2]` Output (one valid ordering): `[[],[1],[2],[1,2],[2,2],[1,2,2]]` ## Clarifications to ask - Are elements guaranteed distinct, or can there be duplicates? - If duplicates exist, should the output contain only unique subsets?

Quick Answer: This question evaluates understanding of power-set generation and handling of duplicate elements, measuring competency in combinatorics, enumeration techniques and algorithmic problem-solving.

Generate all subsets (no duplicates)

Given an integer array `nums` whose elements are all **distinct**, return **all possible subsets** (the power set). The solution may return the subsets in any order. To make grading deterministic, this console expects a canonical form: each subset is sorted in ascending order, and the full list of subsets is sorted by (subset length, then lexicographic order). ### Input - `nums`: an array of distinct integers, length `n` (`0 <= n <= 20`, `-10 <= nums[i] <= 10`). ### Output - A list of lists, where each inner list is a subset of `nums`, in the canonical order described above. ### Example Input: `nums = [1,2,3]` Output: `[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]`

Constraints

0 <= n <= 20
-10 <= nums[i] <= 10
All elements of nums are distinct

Examples

Input: ([1, 2, 3],)

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

Explanation: The power set of {1,2,3}: 2^3 = 8 subsets, in canonical order.

Input: ([],)

Expected Output: [[]]

Explanation: Empty array has exactly one subset: the empty set.

Input: ([0],)

Expected Output: [[], [0]]

Explanation: A single element yields the empty set and the set containing that element.

Input: ([-1, 2],)

Expected Output: [[], [-1], [2], [-1, 2]]

Explanation: Negatives are handled; subsets sorted ascending then by (len, lex).

Input: ([3, 1, 2],)

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

Explanation: Input order does not matter; output is canonicalized to the same result as [1,2,3].

Hints

There are exactly 2^n subsets. Each element is either in a subset or not — that maps directly onto the bits of an integer from 0 to 2^n - 1.
Iterate mask from 0 to (1 << n) - 1; include nums[i] in the current subset when the i-th bit of mask is set.
Sort the input first and sort each subset ascending so the output is deterministic; then sort the list of subsets by (length, lexicographic) to match the expected canonical order.

Generate all unique subsets (may contain duplicates)

Given an integer array `nums` that **may contain duplicate values**, return all **unique** subsets (the power set with no duplicate subsets). The solution may return the subsets in any order. To make grading deterministic, this console expects a canonical form: each subset is sorted in ascending order, and the full list of subsets is sorted by (subset length, then lexicographic order). ### Input - `nums`: an array of integers that may contain duplicates, length `n` (`0 <= n <= 20`, `-10 <= nums[i] <= 10`). ### Output - A list of lists of the **unique** subsets, in the canonical order described above. ### Example Input: `nums = [1,2,2]` Output: `[[],[1],[2],[1,2],[2,2],[1,2,2]]` — note `[2]` appears only once even though there are two 2s.

Constraints

0 <= n <= 20
-10 <= nums[i] <= 10
nums may contain duplicate values; the output must contain no duplicate subsets

Examples

Input: ([1, 2, 2],)

Expected Output: [[], [1], [2], [1, 2], [2, 2], [1, 2, 2]]

Explanation: Two 2s collapse: [2] appears once, and [2,2] is the only subset using both.

Input: ([],)

Expected Output: [[]]

Explanation: Empty array yields only the empty subset.

Input: ([2, 2],)

Expected Output: [[], [2], [2, 2]]

Explanation: Only three unique subsets despite 2^2 = 4 raw masks (the two single-element masks both produce [2]).

Input: ([1, 2, 3],)

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

Explanation: With no duplicates the dup-aware solver returns the full power set, identical to Part A.

Input: ([-1, -1, 2],)

Expected Output: [[], [-1], [2], [-1, -1], [-1, 2], [-1, -1, 2]]

Explanation: Duplicate negatives are deduped just like positives.

Hints

Sort nums first so that equal values are adjacent and every subset, once sorted, has a single canonical representation.
Enumerate all 2^n bitmask subsets exactly as in the distinct case, but dedup the resulting (sorted) subsets — e.g. with a set keyed on the tuple of the subset.
An alternative O(2^n)-without-a-set approach is backtracking: at each index, skip over equal duplicates after the first to avoid generating the same subset twice.
Finish by sorting subsets by (length, lexicographic) to match the canonical output ordering.

Quick Overview

This question evaluates understanding of power-set generation and handling of duplicate elements, measuring competency in combinatorics, enumeration techniques and algorithmic problem-solving.