[DSA][Backtracking] Subsets

Leetcode 78

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.

[Key Idea]
- Explore all possible subsets by considering whether each element is included or not.

Get Woolaf's Techscope’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

[Solution 1] Backtracking

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        subset = []

        def dfs(i):
            if i >= len(nums):
                res.append(subset.copy())
                return
            subset.append(nums[i])
            dfs(i + 1)
            subset.pop()
            dfs(i + 1)

        dfs(0)
        return res

Backtracking is an approach that explores all possible subsets by dividing the search into cases where each element is either included or excluded. This method works recursively by adding an element to the current subset or undoing the selection and returning to the previous state. The key idea is to use pop() to remove the last added element, allowing the algorithm to backtrack and explore other possible combinations once a path has been fully explored.

[Solution 2] Iteration

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]

        for num in nums:
            res += [subset + [num] for subset in res]

        return res

Instead of using recursion, we can solve the problem in the same way using iteration. This approach works by adding each new element to all existing subsets. By using the += operation, we append these newly formed subsets to the result list, effectively generating subsets that both include and exclude the current element at the same time.

[Solution 3] Bit Manipulation

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        for i in range(1 << n):
            subset = [nums[j] for j in range(n) if (i & (1 << j))]
            res.append(subset)
        return res

The bit manipulation approach represents whether each element is included in a subset using binary numbers. If the array has a length of n, we can use all binary numbers from 0 to 2ⁿ - 1 to represent every possible subset. In each binary number, a bit value of 1 means the corresponding element is included, while 0 means it is not.
This allows us to quickly determine whether each element is part of the current subset. By using the expression i & (1 << j), we can check whether the j-th bit of i is set to 1, and if so, include nums[j] in the subset.

⏱️ Time Complexity
Each element has two possible choices — to be included or not — resulting in a total of 2ⁿ combinations. Since generating each subset can take up to n operations (to process all elements), the overall time complexity is O(n × 2ⁿ).

🧠 Space Complexity
We need to store all possible subsets, and there are 2ⁿ subsets in total. Therefore, the overall space complexity is O(2ⁿ).