Complex Algorithmic Challenge

Design an algorithm to solve a complex combination problem for a given input array nums. Calculate how many distinct combinations can select subsets containing at least one element, and the sum of the elements in all subsets must be even. Please write a function to implement the above requirements and provide test cases, ensuring the algorithm's time complexity is preferably lower than $O(2^n)$. Given an integer array nums, return the number of all possible qualifying non-empty subsets. Input Format: The first line is an integer n ($1 \leq n \leq 20$), representing the size of the array. The second line contains n integers, representing elements in the array. Output Format: Output an integer indicating the number of qualified subsets. Sample Input: 3 1 2 3 Sample Output: 4 Constraints: Elements are integers with a value range of $[-10, 10]$. Example Input 3 1 2 3