Count Ways to Assign Unique Cap

🎯

Count Ways to Assign Unique Cap

hardDPGoogle

Imagine a party where each guest wants a unique cap from a collection, but each guest has preferences on which caps they like. How many ways can you assign caps so that everyone gets a unique cap they like?

💡 This problem is a classic example of using bitmask DP to handle combinatorial assignments where each element (person) must be matched uniquely to a subset of options (caps). Beginners often struggle because the problem requires tracking subsets efficiently and understanding how to represent states with bitmasks.

📋

Problem Statement

Given n persons and 100 caps numbered 1 to 100. Each person has a list of caps they like. Find the number of ways to assign caps to persons such that each person gets exactly one cap they like and no two persons get the same cap. Return the count modulo 10^9+7.

1 ≤ n ≤ 10Each person likes at least one capCaps are numbered from 1 to 100

💡

Example

Input"n = 3\nPerson 0 likes caps [5, 100]\nPerson 1 likes caps [1, 5, 100]\nPerson 2 likes caps [1, 2]"

Output4

Possible assignments: (Person0->5, Person1->1, Person2->2), (Person0->5, Person1->100, Person2->1), (Person0->100, Person1->5, Person2->1), (Person0->100, Person1->1, Person2->2)

• All persons like the same single cap → output 0
• Each person likes a unique cap → output 1
• One person likes all caps, others like none → output 0
• Maximum n=10 with overlapping caps → output computed modulo 10^9+7

🔁

Why DP?

Why greedy fails:

A greedy approach assigning caps to persons in order of preference can fail because early assignments may block valid assignments for later persons, leading to suboptimal or zero solutions. For example, if two persons like only cap 1, greedy assigning cap 1 to the first person leaves the second person without any cap.

DP state:

dp[i][mask] represents the number of ways to assign caps to the first i persons where 'mask' is a bitmask representing which caps have already been assigned.

Recurrence:dp[i][mask] = sum over caps c liked by person i and not in mask of dp[i-1][mask without c]

For each person, try all caps they like that are not assigned yet, and sum the ways from previous persons with those caps excluded.

⚠️

Common Mistakes

Not using bitmask to track assigned caps

Leads to incorrect counting or inability to track uniqueness

✅ Use bitmask to represent assigned caps efficiently

Iterating masks forward in space optimized DP

Overcounts ways due to using updated states in same iteration

✅ Iterate masks backwards to preserve previous iteration states

Forgetting modulo operation after additions

Integer overflow or wrong answers

✅ Apply modulo after every addition

Not handling base case correctly

DP returns zero or incorrect counts

✅ Initialize dp[0] = 1 or return 1 when all persons assigned

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's combinatorial nature and why naive recursion is inefficient due to repeated states.

Intuition

Try assigning each cap liked by the current person if it is not already assigned, then recurse for the next person until all are assigned.

Algorithm

1. Start with the first person and an empty set of assigned caps.
2. For the current person, try each cap they like that is not assigned yet.
3. Assign the cap and recurse for the next person.
4. If all persons are assigned, increment the count.

💡 The recursion tree grows exponentially because each person can try multiple caps, and the same states are recomputed multiple times.

Recurrence:ways(i, mask) = sum over caps c liked by person i and not in mask of ways(i+1, mask | (1 << c))

</>

Code

MOD = 10**9 + 7

def count_ways(person_caps, i=0, mask=0, memo=None):
    if memo is None:
        memo = {}
    n = len(person_caps)
    if i == n:
        return 1
    if (i, mask) in memo:
        return memo[(i, mask)]
    ways = 0
    for cap in person_caps[i]:
        if not (mask & (1 << (cap - 1))):
            ways += count_ways(person_caps, i + 1, mask | (1 << (cap - 1)), memo)
            ways %= MOD
    memo[(i, mask)] = ways
    return ways

# Example usage:
if __name__ == '__main__':
    person_caps = [[5, 100], [1, 5, 100], [1, 2]]
    print(count_ways(person_caps))

Line Notes

if memo is None:Initialize memo dictionary only once to store computed states

if i == n:Base case: all persons assigned, count as one valid way

if (i, mask) in memo:Return cached result to avoid recomputation

if not (mask & (1 << (cap - 1)))Check if cap is not assigned yet using bitmask

import java.util.*;

public class CountWaysAssignCap {
    static final int MOD = 1000000007;
    static Map<String, Integer> memo = new HashMap<>();

    public static int countWays(List<List<Integer>> personCaps, int i, int mask) {
        if (i == personCaps.size()) return 1;
        String key = i + "," + mask;
        if (memo.containsKey(key)) return memo.get(key);
        int ways = 0;
        for (int cap : personCaps.get(i)) {
            if ((mask & (1 << (cap - 1))) == 0) {
                ways += countWays(personCaps, i + 1, mask | (1 << (cap - 1)));
                ways %= MOD;
            }
        }
        memo.put(key, ways);
        return ways;
    }

    public static void main(String[] args) {
        List<List<Integer>> personCaps = new ArrayList<>();
        personCaps.add(Arrays.asList(5, 100));
        personCaps.add(Arrays.asList(1, 5, 100));
        personCaps.add(Arrays.asList(1, 2));
        System.out.println(countWays(personCaps, 0, 0));
    }
}

Line Notes

static Map<String, Integer> memo = new HashMap<>();Memoize results for states to avoid recomputation

if (i == personCaps.size()) return 1;Base case: all persons assigned successfully

if ((mask & (1 << (cap - 1))) == 0)Check if cap is free using bitmask

memo.put(key, ways);Store computed ways for current state

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int n;
vector<vector<int>> personCaps;
unordered_map<long long, int> memo;

int countWays(int i, int mask) {
    if (i == n) return 1;
    long long key = ((long long)i << 32) | mask;
    if (memo.count(key)) return memo[key];
    int ways = 0;
    for (int cap : personCaps[i]) {
        if ((mask & (1 << (cap - 1))) == 0) {
            ways += countWays(i + 1, mask | (1 << (cap - 1)));
            ways %= MOD;
        }
    }
    return memo[key] = ways;
}

int main() {
    personCaps = {{5, 100}, {1, 5, 100}, {1, 2}};
    n = (int)personCaps.size();
    cout << countWays(0, 0) << "\n";
    return 0;
}

Line Notes

long long key = ((long long)i << 32) | mask;Combine i and mask into a single key for memoization

if (i == n) return 1;Base case: all persons assigned

if ((mask & (1 << (cap - 1))) == 0)Check if cap is available

return memo[key] = ways;Store and return computed ways for current state

const MOD = 1e9 + 7;

function countWays(personCaps, i = 0, mask = 0, memo = new Map()) {
    if (i === personCaps.length) return 1;
    const key = i + ',' + mask;
    if (memo.has(key)) return memo.get(key);
    let ways = 0;
    for (const cap of personCaps[i]) {
        if ((mask & (1 << (cap - 1))) === 0) {
            ways += countWays(personCaps, i + 1, mask | (1 << (cap - 1)), memo);
            ways %= MOD;
        }
    }
    memo.set(key, ways);
    return ways;
}

// Example usage:
const personCaps = [[5, 100], [1, 5, 100], [1, 2]];
console.log(countWays(personCaps));

Line Notes

if (i === personCaps.length) return 1;Base case: all persons assigned caps

const key = i + ',' + mask;Create unique key for memoization

if ((mask & (1 << (cap - 1))) === 0)Check if cap is free using bitmask

memo.set(key, ways);Cache computed result for current state

⏱

Complexity

TimeO(n * 2^m * k) where n is persons, m is caps, k average caps per person

SpaceO(n * 2^m) for memoization

Each state is defined by person index and assigned caps bitmask; recursion explores all subsets

💡 For n=10 and caps=100, this is huge and impractical, but good to understand problem structure

Interview Verdict: TLE / Use only to introduce problem and motivate DP

This approach is too slow for large inputs but essential to understand before optimizing

🧠

Memoization with Bitmask DP

💡 Memoization avoids recomputing states by caching results, drastically improving efficiency over brute force.

Intuition

Use recursion with memoization to store results for each person and assigned caps bitmask, pruning repeated computations.

Algorithm

1. Initialize a memo dictionary to store results for (person, assigned caps mask).
2. For the current person, iterate over caps they like.
3. If a cap is free, assign it and recurse for the next person.
4. Return the sum of all valid assignments modulo 10^9+7.

💡 Memoization prunes the exponential recursion tree by remembering results for states, making the solution feasible for n up to 10.

Recurrence:dp[i][mask] = sum over caps c liked by person i and not in mask of dp[i+1][mask | (1 << c)]

</>

Code

MOD = 10**9 + 7

def count_ways_memo(person_caps):
    n = len(person_caps)
    memo = {}

    def dfs(i, mask):
        if i == n:
            return 1
        if (i, mask) in memo:
            return memo[(i, mask)]
        ways = 0
        for cap in person_caps[i]:
            bit = 1 << (cap - 1)
            if (mask & bit) == 0:
                ways += dfs(i + 1, mask | bit)
                ways %= MOD
        memo[(i, mask)] = ways
        return ways

    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    person_caps = [[5, 100], [1, 5, 100], [1, 2]]
    print(count_ways_memo(person_caps))

Line Notes

memo = {}Initialize memo dictionary to cache results

if i == n:Base case: all persons assigned

bit = 1 << (cap - 1)Create bitmask for current cap

if (mask & bit) == 0:Check if cap is free before assigning

import java.util.*;

public class CountWaysAssignCapMemo {
    static final int MOD = 1000000007;
    static Map<String, Integer> memo = new HashMap<>();

    public static int dfs(List<List<Integer>> personCaps, int i, int mask) {
        if (i == personCaps.size()) return 1;
        String key = i + "," + mask;
        if (memo.containsKey(key)) return memo.get(key);
        int ways = 0;
        for (int cap : personCaps.get(i)) {
            int bit = 1 << (cap - 1);
            if ((mask & bit) == 0) {
                ways += dfs(personCaps, i + 1, mask | bit);
                ways %= MOD;
            }
        }
        memo.put(key, ways);
        return ways;
    }

    public static void main(String[] args) {
        List<List<Integer>> personCaps = new ArrayList<>();
        personCaps.add(Arrays.asList(5, 100));
        personCaps.add(Arrays.asList(1, 5, 100));
        personCaps.add(Arrays.asList(1, 2));
        System.out.println(dfs(personCaps, 0, 0));
    }
}

Line Notes

static Map<String, Integer> memo = new HashMap<>();Memoize to avoid recomputing states

if (i == personCaps.size()) return 1;Base case: all persons assigned

int bit = 1 << (cap - 1);Bitmask for current cap

if ((mask & bit) == 0)Check if cap is free before assignment

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int n;
vector<vector<int>> personCaps;
unordered_map<long long, int> memo;

int dfs(int i, int mask) {
    if (i == n) return 1;
    long long key = ((long long)i << 32) | mask;
    if (memo.count(key)) return memo[key];
    int ways = 0;
    for (int cap : personCaps[i]) {
        int bit = 1 << (cap - 1);
        if ((mask & bit) == 0) {
            ways += dfs(i + 1, mask | bit);
            ways %= MOD;
        }
    }
    return memo[key] = ways;
}

int main() {
    personCaps = {{5, 100}, {1, 5, 100}, {1, 2}};
    n = (int)personCaps.size();
    cout << dfs(0, 0) << "\n";
    return 0;
}

Line Notes

int bit = 1 << (cap - 1);Create bitmask for current cap

if (i == n) return 1;Base case: all persons assigned

if (memo.count(key)) return memo[key];Return cached result if available

if ((mask & bit) == 0)Check if cap is free before assigning

const MOD = 1e9 + 7;

function countWaysMemo(personCaps) {
    const memo = new Map();
    const n = personCaps.length;

    function dfs(i, mask) {
        if (i === n) return 1;
        const key = i + ',' + mask;
        if (memo.has(key)) return memo.get(key);
        let ways = 0;
        for (const cap of personCaps[i]) {
            const bit = 1 << (cap - 1);
            if ((mask & bit) === 0) {
                ways += dfs(i + 1, mask | bit);
                ways %= MOD;
            }
        }
        memo.set(key, ways);
        return ways;
    }

    return dfs(0, 0);
}

// Example usage
const personCaps = [[5, 100], [1, 5, 100], [1, 2]];
console.log(countWaysMemo(personCaps));

Line Notes

const memo = new Map();Memoize results to avoid recomputation

if (i === n) return 1;Base case: all persons assigned

const bit = 1 << (cap - 1);Bitmask for current cap

if ((mask & bit) === 0)Check if cap is free before assignment

⏱

Complexity

TimeO(n * 2^m * k) with memoization pruning repeated states

SpaceO(n * 2^m) for memo dictionary

Memoization reduces repeated computations but still exponential in worst case

💡 This approach is practical for n up to 10 and caps up to 20-25 due to bitmask size

Interview Verdict: Accepted for small n, practical improvement over brute force

Memoization is the first step to optimize brute force and is often acceptable in interviews

🧠

Tabulation (Bottom-Up Bitmask DP)

💡 Tabulation builds the solution bottom-up, filling a DP table iteratively, which is often easier to debug and understand than recursion.

Intuition

Iteratively compute the number of ways to assign caps to persons by increasing the number of assigned persons, using a DP table indexed by person and assigned caps bitmask.

Algorithm

1. Initialize dp array with dp[0][0] = 1 (no persons assigned, no caps assigned).
2. For each person i from 0 to n-1, iterate over all masks representing assigned caps.
3. For each cap liked by person i, if cap is not assigned in mask, update dp[i+1][mask | (1 << cap)] by adding dp[i][mask].
4. Return dp[n][mask] summed over all masks with n persons assigned.

💡 This approach systematically builds solutions for increasing subsets of persons and assigned caps, ensuring all states are computed once.

Recurrence:dp[i][mask] = sum over caps c liked by person i-1 and not in mask of dp[i-1][mask without c]

</>

Code

MOD = 10**9 + 7

def count_ways_tabulation(person_caps):
    n = len(person_caps)
    dp = [0] * (1 << n)
    dp[0] = 1

    # Create cap to persons mapping for efficiency
    cap_to_persons = [[] for _ in range(101)]
    for i, caps in enumerate(person_caps):
        for c in caps:
            cap_to_persons[c].append(i)

    for cap in range(1, 101):
        new_dp = dp[:]
        for mask in range(1 << n):
            if dp[mask] == 0:
                continue
            for person in cap_to_persons[cap]:
                if (mask & (1 << person)) == 0:
                    new_dp[mask | (1 << person)] = (new_dp[mask | (1 << person)] + dp[mask]) % MOD
        dp = new_dp

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

# Example usage
if __name__ == '__main__':
    person_caps = [[5, 100], [1, 5, 100], [1, 2]]
    print(count_ways_tabulation(person_caps))

Line Notes

dp = [0] * (1 << n)DP array indexed by assigned persons bitmask

dp[0] = 1Base case: no persons assigned, one way

for cap in range(1, 101)Iterate over all caps to assign

new_dp[mask | (1 << person)] = (new_dp[mask | (1 << person)] + dp[mask]) % MODAssign cap to person if free, update ways

import java.util.*;

public class CountWaysAssignCapTab {
    static final int MOD = 1000000007;

    public static int countWays(List<List<Integer>> personCaps) {
        int n = personCaps.size();
        int[] dp = new int[1 << n];
        dp[0] = 1;

        List<List<Integer>> capToPersons = new ArrayList<>();
        for (int i = 0; i <= 100; i++) capToPersons.add(new ArrayList<>());
        for (int i = 0; i < n; i++) {
            for (int c : personCaps.get(i)) {
                capToPersons.get(c).add(i);
            }
        }

        for (int cap = 1; cap <= 100; cap++) {
            int[] newDp = dp.clone();
            for (int mask = 0; mask < (1 << n); mask++) {
                if (dp[mask] == 0) continue;
                for (int person : capToPersons.get(cap)) {
                    if ((mask & (1 << person)) == 0) {
                        newDp[mask | (1 << person)] = (newDp[mask | (1 << person)] + dp[mask]) % MOD;
                    }
                }
            }
            dp = newDp;
        }

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

    public static void main(String[] args) {
        List<List<Integer>> personCaps = new ArrayList<>();
        personCaps.add(Arrays.asList(5, 100));
        personCaps.add(Arrays.asList(1, 5, 100));
        personCaps.add(Arrays.asList(1, 2));
        System.out.println(countWays(personCaps));
    }
}

Line Notes

int[] dp = new int[1 << n];DP array indexed by assigned persons bitmask

dp[0] = 1;Base case: no persons assigned

for (int cap = 1; cap <= 100; cap++)Iterate over all caps

newDp[mask | (1 << person)] = (newDp[mask | (1 << person)] + dp[mask]) % MOD;Assign cap to person if free, update ways

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int countWaysTabulation(const vector<vector<int>>& personCaps) {
    int n = (int)personCaps.size();
    vector<int> dp(1 << n, 0);
    dp[0] = 1;

    vector<vector<int>> capToPersons(101);
    for (int i = 0; i < n; i++) {
        for (int c : personCaps[i]) {
            capToPersons[c].push_back(i);
        }
    }

    for (int cap = 1; cap <= 100; cap++) {
        vector<int> newDp = dp;
        for (int mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] == 0) continue;
            for (int person : capToPersons[cap]) {
                if ((mask & (1 << person)) == 0) {
                    newDp[mask | (1 << person)] = (newDp[mask | (1 << person)] + dp[mask]) % MOD;
                }
            }
        }
        dp = newDp;
    }

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

int main() {
    vector<vector<int>> personCaps = {{5, 100}, {1, 5, 100}, {1, 2}};
    cout << countWaysTabulation(personCaps) << "\n";
    return 0;
}

Line Notes

vector<int> dp(1 << n, 0);DP array indexed by assigned persons bitmask

dp[0] = 1;Base case: no persons assigned

for (int cap = 1; cap <= 100; cap++)Iterate over all caps

newDp[mask | (1 << person)] = (newDp[mask | (1 << person)] + dp[mask]) % MOD;Assign cap to person if free, update ways

const MOD = 1e9 + 7;

function countWaysTabulation(personCaps) {
    const n = personCaps.length;
    let dp = new Array(1 << n).fill(0);
    dp[0] = 1;

    const capToPersons = Array.from({ length: 101 }, () => []);
    for (let i = 0; i < n; i++) {
        for (const c of personCaps[i]) {
            capToPersons[c].push(i);
        }
    }

    for (let cap = 1; cap <= 100; cap++) {
        const newDp = dp.slice();
        for (let mask = 0; mask < (1 << n); mask++) {
            if (dp[mask] === 0) continue;
            for (const person of capToPersons[cap]) {
                if ((mask & (1 << person)) === 0) {
                    newDp[mask | (1 << person)] = (newDp[mask | (1 << person)] + dp[mask]) % MOD;
                }
            }
        }
        dp = newDp;
    }

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

// Example usage
const personCaps = [[5, 100], [1, 5, 100], [1, 2]];
console.log(countWaysTabulation(personCaps));

Line Notes

let dp = new Array(1 << n).fill(0);DP array indexed by assigned persons bitmask

dp[0] = 1;Base case: no persons assigned

for (let cap = 1; cap <= 100; cap++)Iterate over all caps

newDp[mask | (1 << person)] = (newDp[mask | (1 << person)] + dp[mask]) % MOD;Assign cap to person if free, update ways

⏱

Complexity

TimeO(100 * 2^n * n) since we iterate over all caps and subsets of persons

SpaceO(2^n) for dp array

We iterate over all subsets of persons for each cap, updating dp states

💡 For n=10, 2^n=1024, so this is efficient enough for interview constraints

Interview Verdict: Accepted and optimal for given constraints

Tabulation is preferred in interviews for clarity and iterative control

🧠

Space Optimized Tabulation (1D DP with Backward Iteration)

💡 We can optimize space by using a single DP array and iterating masks backwards to avoid overwriting states needed in the same iteration.

Intuition

Since dp[i][mask] depends only on dp[i-1][mask'], we can use one dp array and update it in reverse mask order to preserve previous iteration values.

Algorithm

1. Initialize a 1D dp array with dp[0] = 1.
2. For each cap from 1 to 100, iterate masks backwards from (1 << n) - 1 to 0.
3. For each mask, if dp[mask] > 0, assign cap to any unassigned person and update dp[mask | (1 << person)].
4. Return dp[(1 << n) - 1] as the total number of ways.

💡 Backward iteration ensures that dp updates do not use values updated in the current iteration, preserving correctness.

Recurrence:dp[mask | (1 << person)] += dp[mask] for each cap and person not in mask

</>

Code

MOD = 10**9 + 7

def count_ways_space_optimized(person_caps):
    n = len(person_caps)
    dp = [0] * (1 << n)
    dp[0] = 1

    cap_to_persons = [[] for _ in range(101)]
    for i, caps in enumerate(person_caps):
        for c in caps:
            cap_to_persons[c].append(i)

    for cap in range(1, 101):
        for mask in range((1 << n) - 1, -1, -1):
            if dp[mask] == 0:
                continue
            for person in cap_to_persons[cap]:
                if (mask & (1 << person)) == 0:
                    dp[mask | (1 << person)] = (dp[mask | (1 << person)] + dp[mask]) % MOD

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

# Example usage
if __name__ == '__main__':
    person_caps = [[5, 100], [1, 5, 100], [1, 2]]
    print(count_ways_space_optimized(person_caps))

Line Notes

dp = [0] * (1 << n)Initialize 1D dp array for assigned persons bitmask

dp[0] = 1Base case: no persons assigned

for mask in range((1 << n) - 1, -1, -1)Iterate masks backwards to avoid using updated states

dp[mask | (1 << person)] = (dp[mask | (1 << person)] + dp[mask]) % MODUpdate ways by assigning cap to unassigned person

import java.util.*;

public class CountWaysAssignCapSpaceOpt {
    static final int MOD = 1000000007;

    public static int countWays(List<List<Integer>> personCaps) {
        int n = personCaps.size();
        int[] dp = new int[1 << n];
        dp[0] = 1;

        List<List<Integer>> capToPersons = new ArrayList<>();
        for (int i = 0; i <= 100; i++) capToPersons.add(new ArrayList<>());
        for (int i = 0; i < n; i++) {
            for (int c : personCaps.get(i)) {
                capToPersons.get(c).add(i);
            }
        }

        for (int cap = 1; cap <= 100; cap++) {
            for (int mask = (1 << n) - 1; mask >= 0; mask--) {
                if (dp[mask] == 0) continue;
                for (int person : capToPersons.get(cap)) {
                    if ((mask & (1 << person)) == 0) {
                        dp[mask | (1 << person)] = (dp[mask | (1 << person)] + dp[mask]) % MOD;
                    }
                }
            }
        }

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

    public static void main(String[] args) {
        List<List<Integer>> personCaps = new ArrayList<>();
        personCaps.add(Arrays.asList(5, 100));
        personCaps.add(Arrays.asList(1, 5, 100));
        personCaps.add(Arrays.asList(1, 2));
        System.out.println(countWays(personCaps));
    }
}

Line Notes

int[] dp = new int[1 << n];1D dp array for assigned persons bitmask

dp[0] = 1;Base case: no persons assigned

for (int mask = (1 << n) - 1; mask >= 0; mask--)Backward iteration to avoid using updated states

dp[mask | (1 << person)] = (dp[mask | (1 << person)] + dp[mask]) % MOD;Update ways by assigning cap to unassigned person

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;

int countWaysSpaceOptimized(const vector<vector<int>>& personCaps) {
    int n = (int)personCaps.size();
    vector<int> dp(1 << n, 0);
    dp[0] = 1;

    vector<vector<int>> capToPersons(101);
    for (int i = 0; i < n; i++) {
        for (int c : personCaps[i]) {
            capToPersons[c].push_back(i);
        }
    }

    for (int cap = 1; cap <= 100; cap++) {
        for (int mask = (1 << n) - 1; mask >= 0; mask--) {
            if (dp[mask] == 0) continue;
            for (int person : capToPersons[cap]) {
                if ((mask & (1 << person)) == 0) {
                    dp[mask | (1 << person)] = (dp[mask | (1 << person)] + dp[mask]) % MOD;
                }
            }
        }
    }

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

int main() {
    vector<vector<int>> personCaps = {{5, 100}, {1, 5, 100}, {1, 2}};
    cout << countWaysSpaceOptimized(personCaps) << "\n";
    return 0;
}

Line Notes

vector<int> dp(1 << n, 0);1D dp array for assigned persons bitmask

dp[0] = 1;Base case: no persons assigned

for (int mask = (1 << n) - 1; mask >= 0; mask--)Backward iteration to preserve previous states

dp[mask | (1 << person)] = (dp[mask | (1 << person)] + dp[mask]) % MOD;Update ways by assigning cap to unassigned person

const MOD = 1e9 + 7;

function countWaysSpaceOptimized(personCaps) {
    const n = personCaps.length;
    let dp = new Array(1 << n).fill(0);
    dp[0] = 1;

    const capToPersons = Array.from({ length: 101 }, () => []);
    for (let i = 0; i < n; i++) {
        for (const c of personCaps[i]) {
            capToPersons[c].push(i);
        }
    }

    for (let cap = 1; cap <= 100; cap++) {
        for (let mask = (1 << n) - 1; mask >= 0; mask--) {
            if (dp[mask] === 0) continue;
            for (const person of capToPersons[cap]) {
                if ((mask & (1 << person)) === 0) {
                    dp[mask | (1 << person)] = (dp[mask | (1 << person)] + dp[mask]) % MOD;
                }
            }
        }
    }

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

// Example usage
const personCaps = [[5, 100], [1, 5, 100], [1, 2]];
console.log(countWaysSpaceOptimized(personCaps));

Line Notes

let dp = new Array(1 << n).fill(0);1D dp array for assigned persons bitmask

dp[0] = 1;Base case: no persons assigned

for (let mask = (1 << n) - 1; mask >= 0; mask--)Backward iteration to avoid using updated states

dp[mask | (1 << person)] = (dp[mask | (1 << person)] + dp[mask]) % MOD;Update ways by assigning cap to unassigned person

⏱

Complexity

TimeO(100 * 2^n * n) same as tabulation but less space

SpaceO(2^n) for dp array

Backward iteration allows in-place updates without extra dp arrays

💡 This approach is the most space efficient and preferred in interviews when memory is a concern

Interview Verdict: Accepted and optimal with space optimization

Shows mastery of DP optimization techniques, often impresses interviewers

📊

All Approaches - One-Glance Tradeoffs

💡 Memoization or tabulation with bitmask DP is the best approach to code in interviews for this problem.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n * 2^m * k) exponential	O(n * 2^m)	Yes (deep recursion)	Yes	Mention only - never code
2. Memoization	O(n * 2^m * k) with pruning	O(n * 2^m)	Possible but less than brute force	Yes	Good first optimization to code
3. Tabulation	O(100 * 2^n * n)	O(2^n)	No	Yes	Preferred iterative approach
4. Space Optimized Tabulation	O(100 * 2^n * n)	O(2^n)	No	Yes, with extra bookkeeping	Best for memory constrained scenarios

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and input format.Explain brute force recursion to show problem structure.Introduce memoization to optimize repeated states.Present tabulation as an iterative alternative.Discuss space optimization for advanced mastery.Write clean code and test with examples.

Time Allocation

Clarify: 3min → Approach: 7min → Code: 10min → Test: 5min. Total ~25min

What the Interviewer Tests

Understanding of bitmask DP, ability to optimize recursion, clarity in explaining states and transitions, and coding accuracy.

Common Follow-ups

• What if caps are more than 100? → Use hashing or compress caps.
• Can we reconstruct the assignments? → Yes, by storing parent states.
• What if persons can have multiple caps? → Modify DP to count combinations accordingly.
• How to handle large n? → Problem becomes intractable; heuristic or approximation needed.

💡 These follow-ups test deeper understanding and ability to adapt solutions to variations.

🔍

Pattern Recognition

When to Use

1) Need to assign unique items to persons; 2) Each person has subset preferences; 3) Count number of valid assignments; 4) Constraints small enough for bitmask DP.

Signature Phrases

'each person gets exactly one cap they like''no two persons get the same cap'

NOT This Pattern When

Problems that only require greedy or simple DP without subset uniqueness constraints

Similar Problems

Number of Ways to Wear Different Hats to Each Other - same bitmask DP patternMaximum Bipartite Matching - related combinatorial assignmentAssign Cookies - greedy fails, DP needed

Practice

1. You are given a list of envelopes, each with a width and height. You want to find the maximum number of envelopes you can nest inside each other such that each envelope fits strictly inside the next one by both width and height. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming with nested loops checking all pairs of envelopes for nesting conditions

B. Greedy algorithm that sorts envelopes by width and picks the tallest envelope at each step

C. Sort envelopes by width ascending and height descending, then find the Longest Increasing Subsequence (LIS) on heights using binary search

D. Use a graph and find the longest path by topological sorting

Solution

1. Step 1: Understand problem constraints

   The problem requires strict nesting by both width and height, so sorting by width ascending and height descending ensures envelopes with the same width do not interfere with LIS on height.

2. Step 2: Recognize LIS pattern on heights

   After sorting, the problem reduces to finding the LIS on heights, which can be done optimally with binary search for O(n log n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting by width ascending and height descending + LIS on heights -> optimal solution [OK]

Hint: Sort width asc, height desc, then LIS on height [OK]

Common Mistakes:

• Sorting both width and height ascending causes incorrect LIS
• Using greedy height selection without sorting
• Applying graph longest path without sorting

2. Consider the following Python code implementing the optimal solution for the envelope nesting problem. Given the input [[5,4],[6,4],[6,7],[2,3]], what is the value of the list lis after processing all envelopes?

easy

A. [2, 3, 7]

B. [3, 4, 7]

C. [2, 3, 4, 7]

D. [3, 4]

Solution

1. Step 1: Sort envelopes by width ascending and height descending

   Sorted envelopes: [[2,3],[5,4],[6,7],[6,4]] -> heights = [3,4,7,4]

2. Step 2: Build LIS on heights

   Process heights: 3 -> lis=[3]; 4 -> lis=[3,4]; 7 -> lis=[3,4,7]; 4 -> replace lis[1] with 4 (no change). Final lis = [3,4,7]

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Final lis length 3 matches expected output [OK]

Hint: Trace LIS updates carefully with bisect_left [OK]

Common Mistakes:

• Misplacing elements in lis on equal heights
• Confusing bisect_left with bisect_right
• Not sorting heights correctly

3. You need to find the shortest possible route that visits each city exactly once and returns to the starting city. The number of cities is small (up to 20), and you want an algorithm that efficiently explores all subsets of visited cities while caching intermediate results to avoid recomputation. Which approach best guarantees an optimal solution for this problem?

easy

A. Greedy algorithm that always picks the nearest unvisited city next

B. Dynamic Programming with bitmasking to represent visited subsets and memoize partial paths

C. Simple brute force recursion without memoization to explore all permutations

D. Dijkstra's algorithm to find shortest paths between cities

Solution

1. Step 1: Understand problem constraints

   The problem requires visiting all cities exactly once and returning to start, which is the classic TSP problem.

2. Step 2: Identify suitable algorithm

   Greedy (A) fails to guarantee optimality. Brute force (C) is correct but inefficient. Dijkstra (D) finds shortest paths but not TSP routes. Bitmask DP (B) efficiently encodes visited subsets and caches results, guaranteeing optimality.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Bitmask DP is the standard optimal approach for small TSP [OK]

Hint: Bitmask DP encodes visited sets efficiently [OK]

Common Mistakes:

• Greedy seems intuitive but fails on global optimality

4. Suppose the problem is modified so that nodes can be revisited multiple times without penalty, and the goal is still to find the shortest path visiting all nodes at least once. Which modification to the bottom-up bitmask DP approach is necessary to handle this variant correctly?

hard

A. Remove the bitmask entirely since revisiting nodes is allowed, and run a simple BFS from any node.

B. Use XOR instead of OR to update the visited mask to allow toggling nodes on and off during revisits.

C. Keep the bitmask to track visited nodes but allow transitions that do not change the mask, enabling revisits without penalty.

D. Restart the DP from scratch each time a node is revisited to ensure shortest paths are recalculated.

Solution

1. Step 1: Understand the effect of allowing revisits

   Revisiting nodes is allowed, but the goal remains to visit all nodes at least once, so tracking visited nodes is still necessary.

2. Step 2: Modify DP transitions accordingly

   Transitions must allow moving to neighbors without necessarily changing the visited mask (if revisiting), so the DP must consider states where mask remains the same.

3. Step 3: Confirm correct mask update operation

   Bitmask updates still use OR to add newly visited nodes; revisits do not change the mask.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Allows revisits while correctly tracking visited nodes [OK]

Hint: Allow transitions with unchanged mask to handle revisits [OK]

Common Mistakes:

• Removing bitmask entirely
• Using XOR to toggle visited nodes
• Recomputing DP from scratch on revisits

5. Suppose the Travelling Salesman Problem is modified so that cities can be visited multiple times (revisits allowed). Which of the following changes to the bottom-up bitmask DP approach correctly adapts to this variant?

hard

A. Remove the bitmask representing visited cities and use simple DP over current city and steps taken

B. Keep the bitmask DP as is, since revisits do not affect the visited set representation

C. Use a shortest path algorithm like Floyd-Warshall instead of DP

D. Modify the DP to track the count of visits per city in the state

Solution

1. Step 1: Understand revisits break bitmask usage

   Bitmask DP relies on each city visited exactly once; revisits mean visited set is no longer sufficient to represent state.

2. Step 2: Adapt DP state to allow revisits

   Removing bitmask and using DP over current city and number of steps (or path length) allows revisits, as visited set is not tracked.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask DP is invalid if cities can be revisited [OK]

Hint: Bitmask DP encodes unique visits; revisits require different state [OK]

Common Mistakes:

• Assuming bitmask DP works unchanged with revisits