1. 格雷编码
n 位格雷码序列 是一个由 2n 个整数组成的序列,其中:
- 每个整数都在范围 [0, 2n - 1] 内(含 0 和 2n - 1)
- 第一个整数是 0
- 一个整数在序列中出现 不超过一次
- 每对 相邻 整数的二进制表示 恰好一位不同 ,且
- 第一个 和 最后一个 整数的二进制表示 恰好一位不同
给定一个整数 n ,返回任一有效的 n 位格雷码序列 。
class Solution:def grayCode(self, n: int) -> List[int]:res = [0]for i in range(n):for j in range(len(res) - 1, -1, -1):res.append(res[j] | (1 << i))return res
2. 子集 II
给定一个整数数组 nums ,其中可能包含重复元素,请返回该数组所有可能的 子集(幂集)。
class Solution:def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:nums.sort()res = []def backtrack(start, subset):res.append(subset[:])for i in range(start, len(nums)):if i > start and nums[i] == nums[i - 1]:continuesubset.append(nums[i])backtrack(i + 1, subset)subset.pop()backtrack(0, [])return res