# Count subsets having distinct even numbers

Given a sequence of n numbers. The task is to count all the subsets of the given set which only have even numbers and all are distinct.
Note: By the property of sets, if two subsets have the same set of elements then they are considered as one. For example: [2, 4, 8] and [4, 2, 8] are considered to be the same.

Examples:

```Input : {4, 2, 1, 9, 2, 6, 5, 3}
Output : 7
The subsets are:
[4], [2], [6], [4, 2],
[2, 6], [4, 6], [4, 2, 6]

Input : {10, 3, 4, 2, 4, 20, 10, 6, 8, 14, 2, 6, 9}
Output : 127
```

A simple approach is to consider all the subsets and check whether they satisfy the given conditions or not. The time complexity will be in exponential.

An efficient approach is to count number of distinct even numbers. Let this be ceven. And then apply formula:

2ceven – 1

This is similar to counting the number of subsets of a given set of n elements. 1 is subtracted because the null set is not considered.

## C++

 `// C++ implementation to count subsets having ` `// even numbers only and all are distinct ` `#include ` `using` `namespace` `std; ` ` `  `// function to count the ` `// required subsets ` `int` `countSubsets(``int` `arr[], ``int` `n) ` `{ ` `    ``unordered_set<``int``> us; ` `    ``int` `even_count = 0; ` `         `  `    ``// inserting even numbers in the set 'us' ` `    ``// single copy of each number is retained ` `    ``for` `(``int` `i=0; i:: iterator itr; ` `     `  `    ``// counting distinct even numbers ` `    ``for` `(itr=us.begin(); itr!=us.end(); itr++)         ` `        ``even_count++; ` `     `  `    ``// total count of required subsets ` `    ``return` `(``pow``(2, even_count) - 1); ` `} ` ` `  `// Driver program to test above ` `int` `main() ` `{ ` `    ``int` `arr[] = {4, 2, 1, 9, 2, 6, 5, 3}; ` `    ``int` `n = ``sizeof``(arr) / ``sizeof``(arr[0]); ` `    ``cout << ``"Number of subsets = "` `         ``<< countSubsets(arr, n); ` `    ``return` `0;      ` `}   `

## Java

 `// Java implementation to count subsets having ` `// even numbers only and all are distinct ` `import` `java.util.*; ` ` `  `class` `GFG  ` `{ ` ` `  `// function to count the ` `// required subsets ` `static` `int` `countSubsets(``int` `arr[], ``int` `n) ` `{ ` `    ``HashSet us = ``new` `HashSet<>(); ` `    ``int` `even_count = ``0``; ` `         `  `    ``// inserting even numbers in the set 'us' ` `    ``// single copy of each number is retained ` `    ``for` `(``int` `i = ``0``; i < n; i++) ` `        ``if` `(arr[i] % ``2` `== ``0``) ` `            ``us.add(arr[i]); ` `     `  `     `  `    ``// counting distinct even numbers ` `    ``even_count=us.size(); ` `     `  `    ``// total count of required subsets ` `    ``return` `(``int``) (Math.pow(``2``, even_count) - ``1``); ` `} ` ` `  `// Driver code ` `public` `static` `void` `main(String[] args)  ` `{ ` `    ``int` `arr[] = {``4``, ``2``, ``1``, ``9``, ``2``, ``6``, ``5``, ``3``}; ` `    ``int` `n = arr.length; ` `    ``System.out.println(``"Number of subsets = "` `        ``+ countSubsets(arr, n)); ` `} ` `} ` ` `  `// This code contributed by Rajput-Ji `

## Python3

 `# python implementation to count subsets having  ` `# even numbers only and all are distinct  ` ` `  `#function to count the required subsets  ` `def` `countSubSets(arr, n): ` `    ``us ``=` `set``() ` `    ``even_count ``=` `0` ` `  `    ``# inserting even numbers in the set 'us'  ` `    ``# single copy of each number is retained  ` `    ``for` `i ``in` `range``(n): ` `        ``if` `arr[i] ``%` `2` `=``=` `0``: ` `            ``us.add(arr[i]) ` ` `  `    ``# counting distinct even numbers  ` `    ``for` `i ``in` `us: ` `        ``even_count ``+``=` `1` ` `  `    ``# total count of required subsets  ` `    ``return` `pow``(``2``, even_count)``-`  `1` ` `  ` `  `# Driver program ` `arr ``=` `[``4``, ``2``, ``1``, ``9``, ``2``, ``6``, ``5``, ``3``] ` `n ``=` `len``(arr) ` `print``(``"Numbers of subset="``, countSubSets(arr,n)) ` ` `  `# This code is contributed by Shrikant13 ` ` `

Output:

```Number of subsets = 7
```

Time Complexity: O(n)

## tags:

Arrays Hash subset Arrays Hash subset