Skip to content

Combinatorial Counting

Table of Contents

62. Unique Paths

  • LeetCode | LeetCode CH (Medium)

  • Tags: math, dynamic programming, combinatorics

  • Count the number of unique paths to reach the bottom-right corner of a m x n grid.

62

62. Unique Paths - Python Solution
# DP - 2D
def uniquePaths(m: int, n: int) -> int:
    if m == 1 or n == 1:
        return 1

    dp = [[1] * n for _ in range(m)]

    for i in range(1, m):
        for j in range(1, n):
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

    return dp[-1][-1]


print(uniquePaths(m=3, n=7))  # 28
# [[1, 1, 1,  1,  1,  1,  1],
#  [1, 2, 3,  4,  5,  6,  7],
#  [1, 3, 6, 10, 15, 21, 28]]
62. Unique Paths - C++ Solution
#include <iostream>
#include <vector>
using namespace std;

int uniquePaths(int m, int n) {
    vector dp(m, vector<int>(n, 1));

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
}

int main() {
    int m = 3, n = 7;
    cout << uniquePaths(m, n) << endl;  // 28
    return 0;
}

357. Count Numbers with Unique Digits

1175. Prime Arrangements

3179. Find the N-th Value After K Seconds

1359. Count All Valid Pickup and Delivery Options

2400. Number of Ways to Reach a Position After Exactly k Steps

2514. Count Anagrams

3154. Find Number of Ways to Reach the K-th Stair

  • LeetCode | LeetCode CH (Hard)

  • Tags: math, dynamic programming, bit manipulation, memoization, combinatorics

1643. Kth Smallest Instructions

2842. Count K-Subsequences of a String With Maximum Beauty

1569. Number of Ways to Reorder Array to Get Same BST

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, math, divide and conquer, dynamic programming, tree, union find, binary search tree, memoization, combinatorics, binary tree

3405. Count the Number of Arrays with K Matching Adjacent Elements

1866. Number of Ways to Rearrange Sticks With K Sticks Visible

1467. Probability of a Two Boxes Having The Same Number of Distinct Balls

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, math, dynamic programming, backtracking, combinatorics, probability and statistics

3272. Find the Count of Good Integers

3317. Find the Number of Possible Ways for an Event

1916. Count Ways to Build Rooms in an Ant Colony

  • LeetCode | LeetCode CH (Hard)

  • Tags: math, dynamic programming, tree, graph, topological sort, combinatorics

3343. Count Number of Balanced Permutations

1830. Minimum Number of Operations to Make String Sorted

2954. Count the Number of Infection Sequences

3395. Subsequences with a Unique Middle Mode I

1575. Count All Possible Routes

3251. Find the Count of Monotonic Pairs II

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, math, dynamic programming, combinatorics, prefix sum

2539. Count the Number of Good Subsequences

634. Find the Derangement of An Array

1692. Count Ways to Distribute Candies

Comments