LeetCode 78. Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Both solutions below take O(n*2^n) time.

Using enumerate binary numbers:

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        """Create power set by counting in binary"""
        n = len(nums)
        hi = 1 << n

        subsets = []
        for i in range(hi):
            new_subset = []
            k = 0
            while i > 0:
                if i & 1:
                    new_subset.append(nums[k])

                i >>= 1
                k += 1

            subsets.append(new_subset)

        return subsets

Backtracking:

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(first = 0, curr = []):
            # if the combination is done
            if len(curr) == k:
                output.append(curr[:])
                return
            for i in range(first, n):
                # add nums[i] into the current combination
                curr.append(nums[i])
                # use next integers to complete the combination
                backtrack(i + 1, curr)
                # backtrack
                curr.pop()

        output = []
        n = len(nums)
        for k in range(n + 1):
            backtrack()
        return output

LeetCode 1155. Number of Dice Rolls With Target Sum

You have n dice and each die has k faces numbered from 1 to k.

Given three integers n, k, and target, return the number of possible ways (out of the kn total ways) to roll the dice so the sum of the face-up numbers equals target. Since the answer may be too large, return it modulo 10^9 + 7.

Constraints:

1 <= n, k <= 30
1 <= target <= 1000

from functools import cache

class Solution:
    def numRollsToTarget(self, d: int, f: int, target: int) -> int:

        @cache
        def dfs(t, d):
            if t == 0 and d == 0: return 1
            if d <= 0 or t <= 0: return 0
            return sum(dfs(t-i, d-1) for i in range(1, f+1))

        return dfs(target, d) % int(1e9 + 7)

LeetCode 236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self,
    root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root in (None, p, q):
          return root
        left, right = (self.lowestCommonAncestor(kid, p, q)
                       for kid in (root.left, root.right))
        return root if left and right else left or right

LeetCode 62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to `2

  • 10^9`.
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        @cache
        def dfs(i, j):
            if i >= m or j >= n:      return 0
            if i == m-1 and j == n-1: return 1
            return dfs(i+1, j) + dfs(i, j+1)
        return dfs(0, 0)

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
      """Alternates between two rows"""
        dp = [[1]*n for i in range(2)]
        for i in range(1,m):
            for j in range(1,n):
                dp[i&1][j] = dp[(i-1)&1][j] + dp[i&1][j-1]

        return dp[(m-1)&1][-1]