https://leetcode.com/problems/subsets

In this problem we need to return all posible subsets of given set, and there are a big number of them: 2^n. It usually means, that we need to use some backtracking approach to do it. Let us have function dfs(self, current, nums), with parameters:

  1. current is set of indexes choosen number: we always choose indexes in increasing order.
  2. nums are our original numbers (we can make it global varialbe as well).

Also I start with dummy variable index -1, and when we add subset to final answer, we remove this element. Then we recursively run dfs with new added number i.

Complexity: both time ans space is O(2^n*n), because we have 2^n subsets with n/2 elements in average.

class Solution:
    def subsets(self, nums):
        self.out = []
        self.dfs([-1],nums)
        return self.out

    def dfs(self, current, nums):
        self.out.append([nums[s] for s in current][1:])
        for i in range(current[-1] + 1, len(nums)):
            self.dfs(current + [i], nums)

Oneliners First one is to use combinations library from python, and we itarate over all possible number of elements. Second one uses binary masks.

return chain.from_iterable(combinations(nums, i) for i in range(len(nums)+1))

return [[nums[j] for j in range(len(nums)) if (i&(1<<j))] for i in range(1<<len(nums))]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0078