Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0] Output: [[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10nums are unique.The Subsets problem asks you to generate all possible subsets (the power set) of a given array. Since every element can either be included or excluded, the total number of subsets for an array of size n is 2^n. A common and intuitive way to approach this is through backtracking. You build subsets step-by-step, deciding at each position whether to include the current element, while exploring all possible combinations recursively.
Another efficient technique uses bit manipulation. Since each subset can be represented by a binary number where each bit indicates whether an element is selected, iterating from 0 to 2^n - 1 allows you to construct every subset directly.
Both approaches systematically explore the power set. Backtracking is often easier to understand and extend, while bit manipulation offers a concise and iterative alternative. The total work grows exponentially because every subset must be generated.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Backtracking | O(n * 2^n) | O(n) recursion stack (excluding output) |
| Bit Manipulation | O(n * 2^n) | O(1) auxiliary (excluding output) |
NeetCode
This approach utilizes the concept of recursive backtracking to explore all potential subsets. We start with an empty list and progressively build subsets by either including or excluding each element.
Time Complexity: O(2^n * n), where n is the length of nums. We have 2^n subsets, and copying each subset takes O(n).
Space Complexity: O(n), where n is the depth of the recursion stack.
1#include <stdio.h>
2#include <stdlib.h>
3
4void backtrack(int* nums, int numsSize, int** subsets, int* subset, int start, int* returnSize, int** returnColumnSizes) {
5 subsets[*returnSize] = (int*)malloc(sizeof(int) * numsSize);
6 for (int i = 0; i < start; i++) {
7 subsets[*returnSize][i] = subset[i];
8 }
9 (*returnColumnSizes)[*returnSize] = start;
10 (*returnSize)++;
11
12 for (int i = start; i < numsSize; i++) {
13 subset[start] = nums[i];
14 backtrack(nums, numsSize, subsets, subset, start + 1, returnSize, returnColumnSizes);
15 }
16}
17
18int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
19 int maxSize = 1 << numsSize;
20 int** subsets = (int**)malloc(maxSize * sizeof(int*));
21 int* subset = (int*)malloc(numsSize * sizeof(int));
22 *returnColumnSizes = (int*)malloc(maxSize * sizeof(int));
23 *returnSize = 0;
24
25 backtrack(nums, numsSize, subsets, subset, 0, returnSize, returnColumnSizes);
26
27 free(subset);
28 return subsets;
29}
30
31int main() {
32 int nums[] = {1, 2, 3};
33 int size = 3;
34 int returnSize;
35 int* returnColumnSizes;
36 int** result = subsets(nums, size, &returnSize, &returnColumnSizes);
37
38 for (int i = 0; i < returnSize; i++) {
39 printf("[");
40 for (int j = 0; j < returnColumnSizes[i]; j++) {
41 printf("%d", result[i][j]);
42 if (j < returnColumnSizes[i] - 1) printf(", ");
43 }
44 printf("]\n");
45 free(result[i]);
46 }
47 free(result);
48 free(returnColumnSizes);
49 return 0;
50}
51In this C implementation, we utilize recursive backtracking to explore all possible subsets of the input array. We use a helper function named 'backtrack' which constructs subsets by either including or excluding each element as we proceed through the array.
This approach takes advantage of bit manipulation to enumerate subsets. Each subset can correspond to a binary number where each bit decides if an element is present in the subset:
Time Complexity: O(2^n * n), mapping to subset enumeration.
Space Complexity: O(1), as it utilizes constants.
1#include <stdio.h>
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The most common approach is backtracking, where you recursively decide whether to include each element in the current subset. Another efficient method uses bit manipulation by representing subsets with binary numbers. Both approaches generate all 2^n subsets systematically.
Yes, the Subsets problem is a classic interview question and appears frequently in FAANG-style coding interviews. It tests understanding of recursion, backtracking, and combinatorial generation techniques.
There are 2^n possible subsets for an array of size n. For each subset, up to n elements may be processed or copied, leading to an overall time complexity of O(n * 2^n).
Arrays or lists are typically used to store the current subset during construction. Recursion with a dynamic list works well for backtracking, while bit manipulation iterates through integer masks to determine element inclusion.
This C solution employs bit manipulation. Each subset is represented by a binary counter, where bitwise operations discern element inclusion based on integer value masks at each positional value.