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.
1class Solution:
2 def subsets(self, nums):
3 result = []
4 self.backtrack(nums, 0, [], result)
5 return result
6
7 def backtrack(self, nums, index, current, result):
8 result.append(list(current))
9 for i in range(index, len(nums)):
10 current.append(nums[i])
11 self.backtrack(nums, i + 1, current, result)
12 current.pop()
13
14sol = Solution()
15nums = [1, 2, 3]
16print(sol.subsets(nums))
17This Python solution uses recursive backtracking. The main function generates a list 'result' to accumulate the results, and the backtracking function explores the subsets by deciding to include or exclude each element.
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
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.