You are given an even number of people numPeople that stand around a circle and each person shakes hands with someone else so that there are numPeople / 2 handshakes total.
Return the number of ways these handshakes could occur such that none of the handshakes cross.
Since the answer could be very large, return it modulo 109 + 7.
Example 1:
Input: numPeople = 4 Output: 2 Explanation: There are two ways to do it, the first way is [(1,2),(3,4)] and the second one is [(2,3),(4,1)].
Example 2:
Input: numPeople = 6 Output: 5
Constraints:
2 <= numPeople <= 1000numPeople is even.We design a function dfs(i), which represents the number of handshake schemes for i people. The answer is dfs(n).
The execution logic of the function dfs(i) is as follows:
i \lt 2, then there is only one handshake scheme, which is not to shake hands, so return 1.l, and the number of people on the right be r=i-l-2. Then we have dfs(i)= sum_{l=0}^{i-1} dfs(l) times dfs(r).To avoid repeated calculations, we use the method of memoization search.
The time complexity is O(n^2), and the space complexity is O(n). Where n is the size of numPeople.
Java
C++
Go
TypeScript
Don't Make This Coding Interview Mistake! | Jewels and Stones - Leetcode 771 • Greg Hogg • 443,129 views views
Watch 9 more video solutions →Practice Handshakes That Don't Cross with our built-in code editor and test cases.
Practice on FleetCode