There are n people and 40 types of hats labeled from 1 to 40.
Given a 2D integer array hats, where hats[i] is a list of all hats preferred by the ith person.
Return the number of ways that the n people wear different hats to each other.
Since the answer may be too large, return it modulo 109 + 7.
Example 1:
Input: hats = [[3,4],[4,5],[5]] Output: 1 Explanation: There is only one way to choose hats given the conditions. First person choose hat 3, Second person choose hat 4 and last one hat 5.
Example 2:
Input: hats = [[3,5,1],[3,5]] Output: 4 Explanation: There are 4 ways to choose hats: (3,5), (5,3), (1,3) and (1,5)
Example 3:
Input: hats = [[1,2,3,4],[1,2,3,4],[1,2,3,4],[1,2,3,4]] Output: 24 Explanation: Each person can choose hats labeled from 1 to 4. Number of Permutations of (1,2,3,4) = 24.
Constraints:
n == hats.length1 <= n <= 101 <= hats[i].length <= 401 <= hats[i][j] <= 40hats[i] contains a list of unique integers.This approach involves using backtracking to try all possible assignments of hats by recursively assigning hats to people.
We use memoization to store already computed results to avoid redundant calculations, improving efficiency.
We implemented a `ways` function that checks each hat number iteratively and recursively assigns it to available people.
Using a bit mask helps track which people have already been assigned hats.
Memoization is employed to cache results of previously computed states.
JavaScript
Time Complexity: O(2^n * 40) where `n` is the number of people.
Space Complexity: O(2^n * 40) due to memoization storage.
We use dynamic programming and bitmasking to efficiently calculate the number of distinct hat placements.
Each state is represented by a bitmask indicating which people have been assigned hats.
Transition between states occurs by considering each hat for each person who prefers it.
This C++ solution executes a depth-first search with memoization, similar to backtracking but driven by dynamic programming principles.
It uses bitmasking to determine available states efficiently, and transitions between states by considering hat availability for each person.
Java
Time Complexity: O(2^n * 40)
Space Complexity: O(2^n * 40)
| Approach | Complexity |
|---|---|
| Backtracking with Memoization | Time Complexity: O(2^n * 40) where `n` is the number of people. Space Complexity: O(2^n * 40) due to memoization storage. |
| Dynamic Programming with Bitmasking | Time Complexity: O(2^n * 40) Space Complexity: O(2^n * 40) |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,177 views views
Watch 9 more video solutions →Practice Number of Ways to Wear Different Hats to Each Other with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor