401. 二进制手表

思路

# 思路一:库函数
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        for i in range(len(nums)+1):
            for tmp in itertools.combinations(nums, i):
                res.append(tmp)
        return res

# 思路二:迭代
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = [[]]
        for i in nums:
            res = res + [[i] + num for num in res]
        return res

# 思路三:递归(回溯算法)
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        n = len(nums)
        
        def helper(i, tmp):
            res.append(tmp)
            for j in range(i, n):
                helper(j + 1,tmp + [nums[j]] )
        helper(0, [])
        return res   

一、401. 二进制手表 1.1、题目描述 1.1.1、遍历

class Solution:
    def readBinaryWatch(self, num: int) -> List[str]:
        ret = []
        for i in range(0, 12):
            for j in range(0, 60):
                if self.count1(i) + self.count1(j) == num:
                    if j  int:
        count = 0
        while n != 0:
            if n&1 == 1:
                count += 1
            n >>= 1
        return count

1.1.2、回溯法 二、784. 字母大小写全排列 2.1、题目描述

2.2.1、递归

class Solution:
    def letterCasePermutation(self, S: str) -> List[str]:
        self.__dfs(S, 0, [])
        return self.res
    
    def __init__(self) -> None:
        self.res = []
        
    
    def __dfs(self, S: str, idx: int, path: []) ->None:
        # 结束条件
        if idx == len(S):
            return self.res.append(''.join(path)) 
        
        path.append(S[idx])
        self.__dfs(S, idx+1, path)
        path.pop()

        # 改变大小写
        if S[idx].isalpha():
            path.append(chr(ord(S[idx]) ^ (1 None:
        self.res = []
        
    
    def __dfs(self, size: int, idx: int, path: []) ->None:
        # 结束条件
        if idx == size:
            return self.res.append(''.join(path)) 
        
        self.__dfs(size, idx+1, path)

        # 改变大小写
        if path[idx].isalpha():
            path[idx] = chr(ord(path[idx]) ^ (1 List[List[int]]:
        self.__dfs(0, [], nums)
        return self.res
    
    def __dfs(self, idx: int, path: List[int], nums: List[int]) -> None:
        self.res.append(path)

        for i in range(idx, len(nums)):
            self.__dfs(i+1, path + [nums[i]], nums)        

四、90. 子集 II 4.1、题目描述

4.2.1、排序+回溯

class Solution:
    def __init__(self) -> None:
        self.res = []

    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        # 排序
        nums.sort()
        
        self.__dfs(0, [], nums)
        return self.res
    
    def __dfs(self, idx: int, path: List[int], nums: List[int]) -> None:
        # 和 3.2.1的区别： 判断path是否存在，
        if path not in self.res:
            self.res.append(path)

        for i in range(idx, len(nums)):
            self.__dfs(i+1, path + [nums[i]], nums)    

4.2.2、排序+回溯+剪枝

class Solution:
    def __init__(self) -> None:
        self.res = []

    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        # 排序
        nums.sort()
        
        self.__dfs2(0, [], nums)
        return self.res
    
    def __dfs2(self, idx: int, path: List[int], nums: List[int]) -> None:
        self.res.append(path)

        for i in range(idx, len(nums)):
        	# 加上剪枝操作, 相同层, 如果当前元素与上一个元素相同, 则跳过不遍历以实现剪枝.
            if i > idx and nums[i] == nums[i-1]:
                continue
            self.__dfs2(i+1, path + [nums[i]], nums)