Practice/Amazon/Leetcode 78. Subsets

Leetcode 78. Subsets

CodingMust

Problem

Given an integer array with unique elements, generate all possible subsets (the power set). The output should contain every possible combination of elements from the input array, including the empty subset and the complete array itself.

A subset is a collection of elements from the original array, where order doesn't matter for defining uniqueness. For example, [1, 2] and [2, 1] represent the same subset.

Your solution should return a list containing all subsets. The subsets can be returned in any order.

Requirements

1. Generate all possible subsets including the empty set
2. Each element in the input appears at most once in any subset
3. The order of subsets in the result doesn't matter
4. The order of elements within each subset doesn't matter

Constraints

• 1 ≤ nums.length ≤ 10
• -10 ≤ nums[i] ≤ 10
• All elements in nums are unique
• The exponential time complexity O(2^n) is acceptable given the small input size

Examples

Example 1:

Input: nums = [1, 2, 3] Output: [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]] Explanation: There are 2^3 = 8 total subsets. Each element can either be included or excluded.

Example 2:

Input: nums = [0] Output: [[], [0]] Explanation: Only two subsets exist: the empty set and the set containing the single element.

Example 3:

Input: nums = [5, 2] Output: [[], [5], [2], [5, 2]] Explanation: Four subsets are possible when choosing from two elements.