LC: 1259. Handshakes That Don't Cross - spiralgo/algorithms GitHub Wiki

1259. Handshakes That Don't Cross:

The Essence:

  • Suppose n people stand around a circular table like in the picture below. We have k = n/2 pairs.
  • If Person 1 wants to shake hands with Person X, X should be an even number. Otherwise, the other handshakes would cross.
  • When Person 1 shakes hand with Person X, their 1 pair will split the group into two distinct pairs: j pairs and k-j-1 pairs.
  • Therefore, the number of ways these handshakes could occur will be equal to: numberOfWays(j pairs)*numberOfWays(k-j-1 pairs)

IMG-1713

Details:

For a detailed explanation and DP-Catalan Numbers implementation, please refer to: https://github.com/spiralgo/algorithms/pull/378