Find the powerset of a set
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 resIteratively
Backtracking/dfs:
Bit manipulation:
Related Problems
Given a string S and an integer K, return the length of the longest substring of S that contains at most K distinct characters.
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.
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".
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].