Leetcode Problem 2741. Special Permutations

2741. Special Permutations

Leetcode Solutions

DP with Bitmasking

  1. Initialize a 2D DP array dp with dimensions [1 << n][n] and set all values to 0.
  2. Set dp[1 << i][i] to 1 for all i from 0 to n-1, representing the starting point of permutations.
  3. Iterate over all possible bitmasks mask from 1 to (1 << n) - 1.
  4. For each mask, iterate over all indices i such that nums[i] is included in mask.
  5. For each i, iterate over all indices j such that nums[j] is not included in mask.
  6. If nums[j] is divisible by nums[i] or vice versa, update dp[new_mask][j] where new_mask is mask with the j-th bit set.
  7. The final answer is the sum of dp[(1 << n) - 1][i] for all i.
UML Thumbnail

Recursion with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...