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.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public IList<IList<int>> Subsets(int[] nums) {
6 IList<IList<int>> result = new List<IList<int>>();
7 Backtrack(nums, result, new List<int>(), 0);
8 return result;
9 }
10
11 private void Backtrack(int[] nums, IList<IList<int>> result, List<int> current, int start) {
12 result.Add(new List<int>(current));
13 for (int i = start; i < nums.Length; i++) {
14 current.Add(nums[i]);
15 Backtrack(nums, result, current, i + 1);
16 current.RemoveAt(current.Count - 1);
17 }
18 }
19
20 public static void Main() {
21 Solution sol = new Solution();
22 int[] nums = {1, 2, 3};
23 var result = sol.Subsets(nums);
24
25 foreach (var subset in result) {
26 Console.WriteLine("[" + string.Join(", ", subset) + "]");
27 }
28 }
29}
30Pursuing a recursive method, this C# solution engages a backtracking methodology to embody all subsets. It manages two structures: a running list 'current' for each subset, and 'result' for the aggregate of subsets.
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.
1def subsets(
Python's implementation leverages bitwise operations to enumerate all subsets. Each number from 0 to 2^n - 1 represents a potential subset, interpreted by binary bit positions for index responses.