# 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 res
```

Iteratively

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].