# 78. Subsets

{% embed url="<https://leetcode.com/problems/subsets/>" %}

### Bitmask 位操作

这个其实才是最简单也最适合面试的写法，但对位操作不熟悉，讲不清楚还是算了...

> The idea is that we map each subset to a bitmask of length n, where `1` on the i*th* position in bitmask means the presence of `nums[i]` in the subset, and `0` means its absence.\
> ...\
> It might seem simple at first glance to generate binary numbers, but the real problem here is how to deal with [zero left padding](https://en.wikipedia.org/wiki/Padding_\(cryptography\)#Zero_padding), because one has to generate bitmasks of fixed length, *i.e.* `001` and not just `1`. For that one could use standard bit manipulation trick.

即用 bin 函数来生成一个 bitmask，但是需要舍弃掉前三位的占位符（padding）：

```python
for i in range(2**n, 2**(n + 1)):
    # generate bitmask, from 0..00 to 1..11
    bitmask = bin(i)[3:]
    # bin(i)      ->   01b001
    # bin(i)[3:]  ->   001
```

### Backtracking

已知合格判断：子集长度只可能是range(0, n+1)。那就用 backtracking，探索所有可能的case，达到要求（长度=k）时记录，否则继续朝下探索。

### Cascading

比较笨拙的一个方法，power set从空集开始，依次从nums中加入单个元素x构成的集合`[x]`，`[x]`被加入时，将它与 power set 中已经存在的每一个子集都合并一次，然后把得到的新集合也作为子集加入 power set.

{% tabs %}
{% tab title="Bitmask" %}

```python
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        output = []
        
        for i in range(2**n, 2**(n + 1)):
            # generate bitmask, from 0..00 to 1..11
            bitmask = bin(i)[3:]
            
            # append subset corresponding to that bitmask
            output.append([nums[j] for j in range(n) if bitmask[j] == '1'])
        
        return output
```

{% endtab %}

{% tab title="Backtracking" %}

```python
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
    
        def backtrack(array, path, k):
            if len(path) == k:
                res.append(path)
            else:
                for i in range(len(array)):
                    backtrack(array[i+1:], path+[array[i]], k)
                    
        for k in range(len(nums)+1):
            backtrack(nums, [], k)
            
        return res
            
```

{% endtab %}

{% tab title="Cascading" %}

```python
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
    
        for x in nums:
            cascade = []
            for subset in res:
                cascade.append([x] + subset)
            res.extend(cascade)
            
        return res
        
        
## or write in a more simple way:

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
    
        for x in nums:
            res.extend([[x]+subset for subset in res])
            
        return res
```

{% endtab %}

{% tab title="JavaScript-Backtracking" %}

```javascript
function getAllCombinations(str) {
    charArr = str.split('');
    let res=[];
	let auxArr = [];
    function dfs(charArr, curr, k) {
        if(charArr.length === k) {
            res.push(curr); 
        } else {
        dfs(charArr, [...curr, charArr[k]], k+1);
        dfs(charArr, curr, k+1);
        }
    }
    dfs(charArr, auxArr, 0)
    return res
}
```

{% endtab %}
{% endtabs %}
