Sponsored
Sponsored
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.
1import java.
The Java implementation harnesses bit masking to derive subsets. 'subsetCount' calculates the potential number of subsets, and looping over this map aids complete subset extraction.