78. Subsets

Loading...LeetCode

Bitmask 位操作

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

The idea is that we map each subset to a bitmask of length n, where 1 on the ith 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, 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）：

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.

Bitmask

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

Backtracking

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
            

Cascading

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

JavaScript-Backtracking

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
}