Split Array into Consecutive Subsequences

In Doudizhu, cards with consecutive ranks can form straights. Sometimes splitting pairs to combine with single cards allows forming more straights, potentially increasing winning chances.

How can we optimally split cards to form straights? Let's explore an interesting algorithm problem: consecutive subsequence partition.

This is LeetCode problem 659 "Split Array into Consecutive Subsequences":

Given a sorted array nums in ascending order (possibly containing duplicates), determine whether it can be partitioned into subsequences where each subsequence:

• Has length ≥ 3
• Consists of consecutive integers

Function signature:

boolean isPossible(int[] nums);

bool isPossible(vector<int>& nums);

def isPossible(nums: List[int]) -> bool:

func isPossible(nums []int) bool

var isPossible = function(nums) {}

For example, consider the given input nums = [1,2,3,3,4,4,5,5]. The algorithm returns true.

This is because nums can be split into two subsequences of consecutive integers: [1,2,3,4,5] and [3,4,5].

However, if the input is nums = [1,2,3,4,4,5], the algorithm returns false, as it cannot be split into two subsequences of at least length 3 with consecutive integers.

For problems involving consecutive integers, sorting should be your first instinct. But in this case, the problem states that the input nums is already sorted.

So, how do we determine if nums can be divided into several subsequences that meet the criteria?

Similar to the previous article on Backtracking for Set Partitioning, we want to partition the elements of nums into several subsequences. The logic can be represented by the following code: