Skip to main content

Pattern 7: Bitmask & Digit DP

The Pattern​

Core Insight

State encodes complex information using bitmasks or digit manipulation:

  • Bitmask DP: State = dp[mask] or dp[mask][i] where mask represents a subset
  • Digit DP: State = dp[pos][mask][tight] where we build numbers digit by digit

Both handle exponential state spaces efficiently for their specific problem types.

Two Main Subtypes​

Type 1: Bitmask DP (Subset Problems)​

When to Use Bitmask DP
  • Small set of items (n ≤ 20 typically)
  • Need to track "which subset is used/visited/assigned"
  • Permutation/combination problems with constraints
  • Key: Encode subset as integer bitmask → O(2^n) states become manageable

Classic Structure:

// Bitmask DP Template
for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) == 0) { // i not in mask
            int newMask = mask | (1 << i); // add i to mask
            dp[newMask] = best(dp[newMask], dp[mask] + cost(i));
        }
    }
}

Key Bit Operations:

// Check if bit i is set
boolean isSet = (mask & (1 << i)) != 0;

// Set bit i (add i to subset)
int newMask = mask | (1 << i);

// Clear bit i (remove i from subset)
int cleared = mask & ~(1 << i);

// Count set bits
int count = Integer.bitCount(mask);

// All bits set (full subset)
int fullMask = (1 << n) - 1;

Type 2: Digit DP (Number Construction)​

When to Use Digit DP
  • Count numbers in range [L, R] with specific properties
  • Build numbers digit by digit with constraints
  • Constraints on digit choices (unique, stepping, specific digits allowed)
  • Works efficiently even for huge numbers (up to 10^18)

Classic Structure:

// Digit DP Template
int digitDP(int pos, int mask, boolean tight, boolean started) {
    // pos: current position building number
    // mask: which digits used (for uniqueness constraints)
    // tight: still bounded by upper limit
    // started: has placed non-zero digit (handles leading zeros)

    if (pos == len) return started ? 1 : 0;
    if (memo[pos][mask][tight ? 1 : 0][started ? 1 : 0] != -1)
        return memo[pos][mask][tight ? 1 : 0][started ? 1 : 0];

    int limit = tight ? digits[pos] : 9;
    int result = 0;

    for (int digit = 0; digit <= limit; digit++) {
        if (!started && digit == 0) {
            // Leading zero - don't update mask
            result += digitDP(pos+1, mask, false, false);
        } else if ((mask & (1 << digit)) == 0) {
            // Digit not used yet (for uniqueness)
            result += digitDP(pos+1, mask | (1<<digit),
                            tight && (digit==limit), true);
        }
    }

    return memo[pos][mask][tight ? 1 : 0][started ? 1 : 0] = result;
}

20 Problems by Category​

Category 1: Pure Bitmask DP (Subset Problems)​

1. Traveling Salesman Problem (TSP) ⭐⭐⭐​

THE Classic Bitmask DP Problem

State: dp[mask][i] = minimum cost to visit cities in mask, currently at city i

WHAT IDENTIFIES A UNIQUE SUBPROBLEM?

  • Parameters: (mask, currentCity) - which cities visited + where we are now
  • State Space: O(2^n × n) - manageable for n ≤ 20
  • Why it works: Subset of visited cities encoded in single integer
class TSP {
    public int tsp(int[][] dist) {
        int n = dist.length;
        int[][] dp = new int[1 << n][n];

        // Initialize with infinity
        for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);

        // Start at city 0
        dp[1][0] = 0;

        // Iterate through all possible masks
        for (int mask = 1; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) == 0) continue; // i not visited

                // Try going to unvisited city j
                for (int j = 0; j < n; j++) {
                    if ((mask & (1 << j)) != 0) continue; // j already visited

                    int newMask = mask | (1 << j);
                    dp[newMask][j] = Math.min(dp[newMask][j],
                                              dp[mask][i] + dist[i][j]);
                }
            }
        }

        // Return to starting city
        int fullMask = (1 << n) - 1;
        int result = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            result = Math.min(result, dp[fullMask][i] + dist[i][0]);
        }

        return result;
    }
}

Time: O(2^n × n²), Space: O(2^n × n) Works for n ≤ 20. For larger n, need approximation algorithms.

2. Shortest Path Visiting All Nodes (LC 847) ⭐⭐​

Problem: Graph with n nodes. Find shortest path visiting all nodes (can revisit).

class Solution {
    public int shortestPathLength(int[][] graph) {
        int n = graph.length;
        int fullMask = (1 << n) - 1;

        // BFS with state (node, visited_mask)
        Queue<int[]> queue = new LinkedList<>();
        boolean[][] visited = new boolean[n][1 << n];

        // Start from all nodes
        for (int i = 0; i < n; i++) {
            queue.offer(new int[]{i, 1 << i, 0}); // node, mask, dist
            visited[i][1 << i] = true;
        }

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int node = curr[0], mask = curr[1], dist = curr[2];

            if (mask == fullMask) return dist;

            for (int next : graph[node]) {
                int newMask = mask | (1 << next);
                if (!visited[next][newMask]) {
                    visited[next][newMask] = true;
                    queue.offer(new int[]{next, newMask, dist + 1});
                }
            }
        }

        return -1;
    }
}

State: (node, visited_set). BFS finds shortest path naturally. Time: O(2^n × n²), Space: O(2^n × n)

3. Partition to K Equal Sum Subsets (LC 698) ⭐⭐​

Problem: Can we partition array into k subsets with equal sum?

class Solution {
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum = Arrays.stream(nums).sum();
        if (sum % k != 0) return false;

        int target = sum / k;
        int n = nums.length;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == -1) continue;

            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) continue; // already used

                int newMask = mask | (1 << i);
                int newSum = dp[mask] + nums[i];

                if (newSum <= target) {
                    // If we complete a subset, reset sum to 0
                    dp[newMask] = Math.max(dp[newMask], newSum % target);
                }
            }
        }

        return dp[(1 << n) - 1] == 0;
    }
}

Trick: dp[mask] stores current subset sum modulo target. When we complete a subset (sum = target), reset to 0.

4. Maximum Students Taking Exam (LC 1349) ⭐⭐⭐​

Problem: Place students in seats (grid with broken seats). No cheating (can't see adjacent/diagonal).

class Solution {
    public int maxStudents(char[][] seats) {
        int m = seats.length, n = seats[0].length;
        int[] validMasks = new int[m];

        // Precompute valid masks for each row
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (seats[i][j] == '.') {
                    validMasks[i] |= (1 << j);
                }
            }
        }

        int[][] dp = new int[m][1 << n];
        for (int[] row : dp) Arrays.fill(row, -1);

        return solve(0, 0, seats, validMasks, dp, m, n);
    }

    private int solve(int row, int prevMask, char[][] seats,
                      int[] validMasks, int[][] dp, int m, int n) {
        if (row == m) return 0;
        if (dp[row][prevMask] != -1) return dp[row][prevMask];

        int maxStudents = 0;
        int validMask = validMasks[row];

        // Try all possible seating arrangements for current row
        for (int mask = 0; mask <= validMask; mask++) {
            if ((mask & validMask) != mask) continue; // invalid seats
            if (!isValidRow(mask, n)) continue; // students adjacent in row
            if (!isCompatible(mask, prevMask, n)) continue; // diagonal cheating

            int students = Integer.bitCount(mask);
            maxStudents = Math.max(maxStudents,
                students + solve(row + 1, mask, seats, validMasks, dp, m, n));
        }

        return dp[row][prevMask] = maxStudents;
    }

    private boolean isValidRow(int mask, int n) {
        // No two adjacent students in same row
        return (mask & (mask << 1)) == 0;
    }

    private boolean isCompatible(int currMask, int prevMask, int n) {
        // No diagonal cheating
        return (currMask & (prevMask << 1)) == 0 &&
               (currMask & (prevMask >> 1)) == 0;
    }
}

State: (row, previous_row_mask). Check adjacency and diagonal constraints.

5-10. More Bitmask Problems​

5. Minimum Cost to Connect Two Groups (LC 1595)

  • dp[i][mask] = min cost connecting first i from group1 to subset mask of group2

6. Fair Distribution of Cookies (LC 2305)

  • dp[mask][k] = min unfairness distributing cookies in mask to k children

7. Number of Ways to Wear Different Hats (LC 1434)

  • dp[mask] = ways to assign hats to people in mask
  • Iterate through hats, assign to available people

8. Minimum XOR Sum of Two Arrays (LC 1879)

  • dp[i][mask] = min XOR sum pairing first i elements with subset mask

9. Find Minimum Time to Finish All Jobs (LC 1723)

  • Binary search on time + bitmask feasibility check

10. Can I Win (LC 464)

  • Game theory + bitmask for used numbers
  • dp[mask][total] = can current player win

Category 2: Digit DP (Number Construction)​

11. Count Numbers with Unique Digits (LC 357) ⭐⭐​

Problem: Count numbers in [0, n] with all unique digits.

class Solution {
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) return 1;

        // For n digits: first digit has 9 choices (1-9)
        // Each subsequent digit has decreasing choices
        int result = 10; // numbers 0-9
        int uniqueDigits = 9;
        int availableDigits = 9;

        for (int i = 2; i <= n && availableDigits > 0; i++) {
            uniqueDigits *= availableDigits;
            result += uniqueDigits;
            availableDigits--;
        }

        return result;
    }
}

Math Insight: For n digits, answer = 9 × 9 × 8 × 7 × ... (combinatorics) But digit DP approach generalizes to complex constraints!

12. Numbers At Most N Given Digit Set (LC 902) ⭐⭐​

Problem: Count numbers ≤ n using only digits from given set.

class Solution {
    public int atMostNGivenDigitSet(String[] digits, int n) {
        String numStr = String.valueOf(n);
        int len = numStr.length();
        int digitCount = digits.length;

        // Count numbers with fewer digits
        int result = 0;
        for (int i = 1; i < len; i++) {
            result += (int) Math.pow(digitCount, i);
        }

        // Count numbers with same number of digits
        for (int i = 0; i < len; i++) {
            boolean hasSameDigit = false;
            for (String d : digits) {
                if (d.charAt(0) < numStr.charAt(i)) {
                    result += (int) Math.pow(digitCount, len - i - 1);
                } else if (d.charAt(0) == numStr.charAt(i)) {
                    hasSameDigit = true;
                    break;
                }
            }
            if (!hasSameDigit) return result;
        }

        return result + 1; // n itself is valid
    }
}

13. Numbers With Repeated Digits (LC 1012) ⭐⭐⭐​

Problem: Count numbers in [1, n] with at least one repeated digit.

Digit DP Template in Action

This is the PERFECT problem to see full digit DP template!

class Solution {
    private Integer[][][] memo;
    private char[] digits;

    public int numDupDigitsAtMostN(int n) {
        digits = String.valueOf(n).toCharArray();
        int len = digits.length;

        // memo[pos][mask][tight]
        memo = new Integer[len][1 << 10][2];

        // Total - unique = repeated
        return n - countUnique(0, 0, true, false);
    }

    private int countUnique(int pos, int mask, boolean tight, boolean started) {
        if (pos == digits.length) return started ? 1 : 0;

        int tightIdx = tight ? 1 : 0;
        if (memo[pos][mask][tightIdx] != null)
            return memo[pos][mask][tightIdx];

        int limit = tight ? (digits[pos] - '0') : 9;
        int result = 0;

        for (int digit = 0; digit <= limit; digit++) {
            if (!started && digit == 0) {
                // Leading zero - don't mark as used
                result += countUnique(pos + 1, mask, false, false);
            } else if ((mask & (1 << digit)) == 0) {
                // Digit not used yet
                result += countUnique(pos + 1, mask | (1 << digit),
                                    tight && (digit == limit), true);
            }
        }

        return memo[pos][mask][tightIdx] = result;
    }
}

Key Parameters Explained:

  • pos: Current position building number (0 to len-1)
  • mask: Bitmask of digits already used (for uniqueness)
  • tight: Are we still bounded by upper limit n?
  • started: Have we placed a non-zero digit? (handles leading zeros)

14. Non-negative Integers without Consecutive Ones (LC 600) ⭐⭐​

Problem: Count numbers ≤ n with no consecutive 1s in binary representation.

class Solution {
    private Integer[][] memo;

    public int findIntegers(int n) {
        String binary = Integer.toBinaryString(n);
        memo = new Integer[binary.length()][2];
        return dp(0, 0, true, binary);
    }

    private int dp(int pos, int prevBit, boolean tight, String binary) {
        if (pos == binary.length()) return 1;
        if (memo[pos][tight ? 1 : 0] != null)
            return memo[pos][tight ? 1 : 0];

        int limit = tight ? (binary.charAt(pos) - '0') : 1;
        int result = 0;

        for (int bit = 0; bit <= limit; bit++) {
            if (prevBit == 1 && bit == 1) continue; // consecutive 1s
            result += dp(pos + 1, bit, tight && (bit == limit), binary);
        }

        return memo[pos][tight ? 1 : 0] = result;
    }
}

15-20. More Digit DP Problems​

15. Count Special Integers (LC 2376)

  • Count integers in range with unique digits
  • Full digit DP template with mask tracking

16. Count Stepping Numbers in Range (LC 2801)

  • Adjacent digits differ by exactly 1
  • dp[pos][last_digit][tight]

17. Number of Digit One (LC 233)

  • Count total occurrences of digit 1 in [1, n]
  • dp[pos][count][tight] = numbers with exactly count 1s

18. Digit Count in Range (LC 1067)

  • Similar to above but for any digit d

19. K-th Smallest in Lexicographical Order (LC 440)

  • Not pure digit DP but similar tree traversal
  • Count numbers in each subtree of digit trie

20. Find the Count of Numbers Which Are Not Special (LC 3233)

  • Digit DP with special number detection
  • Count valid numbers in range with properties

Recognition Checklist​

Use Bitmask DP When You See:​

Bitmask Triggers

✅ "Visit all nodes/cities" → TSP pattern ✅ "Assign items to groups" → assignment with mask ✅ "Select subset with constraints" → track which items used ✅ Small n (≤ 20) with exponential states ✅ "Permutation/combination with complex rules"

Use Digit DP When You See:​

Digit DP Triggers

✅ "Count numbers in range [L, R] with property X" ✅ "Numbers with unique/specific digits" ✅ "Binary numbers without consecutive 1s" ✅ "Stepping numbers" or similar digit constraints ✅ Works even for huge ranges (up to 10^18)

Master Templates​

Bitmask DP Template​

class BitmaskDP {
    public int solve(int[] items) {
        int n = items.length;
        int[] dp = new int[1 << n];
        Arrays.fill(dp, Integer.MAX_VALUE / 2);
        dp[0] = 0;

        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == Integer.MAX_VALUE / 2) continue;

            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) continue; // already used

                int newMask = mask | (1 << i);
                dp[newMask] = Math.min(dp[newMask],
                                      dp[mask] + cost(items, mask, i));
            }
        }

        return dp[(1 << n) - 1];
    }

    private int cost(int[] items, int mask, int item) {
        // Calculate cost of adding item to current state
        return 0;
    }
}

Digit DP Template​

class DigitDP {
    private Integer[][][][] memo;
    private char[] digits;

    public int countNumbers(int n) {
        digits = String.valueOf(n).toCharArray();
        int len = digits.length;
        memo = new Integer[len][1 << 10][2][2]; // pos, mask, tight, started

        return dp(0, 0, true, false);
    }

    private int dp(int pos, int mask, boolean tight, boolean started) {
        if (pos == digits.length) return started ? 1 : 0;

        int t = tight ? 1 : 0, s = started ? 1 : 0;
        if (memo[pos][mask][t][s] != null) return memo[pos][mask][t][s];

        int limit = tight ? (digits[pos] - '0') : 9;
        int result = 0;

        for (int digit = 0; digit <= limit; digit++) {
            if (!started && digit == 0) {
                // Leading zero
                result += dp(pos + 1, mask, false, false);
            } else if (isValid(digit, mask)) {
                // Check constraints
                int newMask = updateMask(mask, digit);
                result += dp(pos + 1, newMask,
                           tight && (digit == limit), true);
            }
        }

        return memo[pos][mask][t][s] = result;
    }

    private boolean isValid(int digit, int mask) {
        // Check if digit satisfies constraints given current mask
        return true;
    }

    private int updateMask(int mask, int digit) {
        // Update mask based on digit added
        return mask | (1 << digit);
    }
}

Complexity Analysis​

Bitmask DP​

  • State Space: O(2^n × other_dimensions)
  • TSP: O(2^n × n²) time, O(2^n × n) space
  • Feasible for: n ≤ 20 typically (2^20 ≈ 1 million)
  • Bottleneck: Exponential states, but each state computed once

Digit DP​

  • State Space: O(digits × 2^10 × 2 × 2)
  • Typical: O(18 × 1024 × 4) ≈ 70K states for numbers up to 10^18
  • Extremely Efficient: Even for huge numbers!
  • Key: Number of digits is logarithmic in n

Key Insights​

Critical Understanding

Bitmask DP:

If you need to track "which subset of items" and n is small, encode the subset as a bitmask. This turns exponential states (2^n) into manageable DP.

Digit DP:

Build numbers digit by digit from left to right. The tight flag ensures you don't exceed the upper bound. The started flag handles leading zeros correctly.

Both patterns handle seemingly exponential state spaces efficiently for their specific problem types!

Practice Path​

  1. Start with Bitmask: TSP, Shortest Path All Nodes, Partition K Subsets
  2. Master Digit DP: Numbers with Repeated Digits (LC 1012) - the template
  3. Combine Techniques: Problems using both (mask for digits + digit construction)
  4. Advanced: Game theory + bitmask, Multi-dimensional bitmask DP

Time Investment:

  • Master bitmask basics: 5-7 problems
  • Master digit DP template: 3-5 problems
  • Total: ~10-12 problems to unlock pattern recognition

Congratulations! 🎉​

You've now completed all 7 core Dynamic Programming patterns:

  1. ✅ Linear Sequence Decision
  2. ✅ Grid Traversal
  3. ✅ Bounded Knapsack
  4. ✅ Interval DP
  5. ✅ State Machine
  6. ✅ Tree DP
  7. ✅ Bitmask & Digit DP ← You are here!

You now have a complete DP arsenal covering 120+ problems across every major pattern. With these patterns mastered, you can recognize and solve 90%+ of DP problems you'll encounter!

Next Level: Combine patterns! Many hard problems use 2-3 patterns together (e.g., Tree DP + Bitmask, Interval DP + State Machine).