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.
1const subsets = (nums) => {
2 const result = [];
3 const backtrack = (index, current) => {
4 result.push([...current]);
5 for (let i = index; i < nums.length; i++) {
6 current.push(nums[i]);
7 backtrack(i + 1, current);
8 current.pop();
9 }
10 };
11 backtrack(0, []);
12 return result;
13};
14
15const nums = [1, 2, 3];
16console.log(subsets(nums));
17This JavaScript implementation utilizes closure and recursion to achieve subset generation. The 'backtrack' function maintains an ongoing state of recursion depth and utilises backtracking to manage element inclusions/exclusions
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.
1using System;
2using System.Collections.Generic;
public class Solution {
public IList<IList<int>> Subsets(int[] nums) {
IList<IList<int>> result = new List<IList<int>>();
int subsetCount = 1 << nums.Length;
for (int i = 0; i < subsetCount; i++) {
List<int> subset = new List<int>();
for (int j = 0; j < nums.Length; j++) {
if ((i & (1 << j)) > 0) {
subset.Add(nums[j]);
}
}
result.Add(subset);
}
return result;
}
public static void Main() {
Solution sol = new Solution();
int[] nums = {1, 2, 3};
var result = sol.Subsets(nums);
foreach (var subset in result) {
Console.WriteLine("[" + string.Join(", ", subset) + "]");
}
}
}
This C# approach again utilizes bit manipulation, where all prospective subsets map to binary representations gated by mask checks, ultimately affirming element adherence within emergent subsets.