Find the powerset of a set

Home | Coding Interviews | Arrays and Strings | Find the powerset of a set

Arrays and Strings Medium Video Python Code Solution

Given a set of distinct integers, return the power set (all possible subsets including the empty set)

There are a few ways to approach finding the powerset.

class Solution(object):
    def subsets(self, nums):
        ret = []
        self.dfs(nums, [], ret)
        return ret
    
    def dfs(self, nums, path, ret):
        ret.append(path)
        for i in range(len(nums)):
            self.dfs(nums[i+1:], path+[nums[i]], ret)
       
    # Bit Manipulation    
    def subsets2(self, nums):
        res = []
        nums.sort()
        for i in xrange(1<<len(nums)):
            tmp = []
            for j in xrange(len(nums)):
                if i & 1 << j:  # if i >> j & 1:
                    tmp.append(nums[j])
            res.append(tmp)
        return res
		
    # Iteratively
    def subsets(self, nums):
        res = [[]]
        for num in sorted(nums):
            res += [item+[num] for item in res]
        return res

Iteratively

Backtracking/dfs:

Bit manipulation:

Posted by Jamie Meyer 9 months ago

Related Problems

Longest Substring with At Most K Distinct Characters

Given a string S and an integer K, return the length of the longest substring of S that contains at most K distinct characters.

Arrays and Strings Medium Video Code Solution Java

Shortest Unsorted Continuous Subarray

Given an integer array nums, you need to find one continuous subarray such that if you only sort this subarray in non-decreasing order, then the whole array will be sorted in non-decreasing order.

Return the shortest such subarray and output its length.

Arrays and Strings Medium Video Code Solution Java

Jewels and Stones

You're given strings jewels representing the types of stones that are jewels, and stones representing the stones you have. Each character in stones is a type of stone you have. You want to know how many of the stones you have are also jewels.

Letters are case sensitive, so "a" is considered a different type of stone from "A".

Arrays and Strings Easy Video Code Solution Java

Decode String

Given an encoded string, return its decoded string.

The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc. Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].

Arrays and Strings Medium Video Python Code Solution