As we mentioned earlier, bitwise operations can be used to find number of subsets. Here, we will use that.
Given an array arr of N elements. The task is to count all the subsets whose sum is even.
Example:
Input:N = 3
arr[] = 1 2 3
Output:3
Explanation: Three subsets are there whose sum of elements is even. Subsets are (3, 2, 1), (1, 3), (2).
 
Your Task:
Your task is to complete the function countSumSubsets() which counts all the subsets in which sum of all the elements is even. Print the count of subsets whose sum of all elements is even.
Constraints:
1 <= N <= 10
1 <= arr[i] <= 10

Source: geeksforgeeks | Difficulty: EASY
Tags: Bit manipulation

Data structures

Starter code: #User function Template for python3



class Solution:

	def countSumSubsets(self, arr, N):

		#Code here

Solutions:
import itertools

class Solution:

	def countSumSubsets(self, arr, N):
		lst = []
		tmp = []

		def subs(idx, arr, N, tmp, lst, sm):
			if idx >= N:
				if sum(tmp) % 2 == 0:
					lst.append(tmp[:])
				return
			tmp.append(arr[idx])
			subs(idx + 1, arr, N, tmp, lst, sm)
			tmp.pop()
			subs(idx + 1, arr, N, tmp, lst, sm)
		subs(0, arr, N, tmp, lst, 0)
		return len(lst) - 1


class Solution:

	def countSumSubsets(self, arr, N):
		cnt = []
		sm = 0

		def subs(idx, arr, N, sm, cnt):
			if idx >= N:
				if sm % 2 == 0:
					c = [1]
					cnt.append(c[:])
				return
			sm += arr[idx]
			subs(idx + 1, arr, N, sm, cnt)
			sm -= arr[idx]
			subs(idx + 1, arr, N, sm, cnt)
		subs(0, arr, N, sm, cnt)
		return len(cnt) - 1


class Solution:

	def countSumSubsets(self, arr, N):
		even = 0
		odd = 0
		for item in arr:
			even += item % 2 == 0
			odd += item % 2
		if odd:
			even += odd - 1
		return 2 ** even - 1


class Solution:

	def countSumSubsets(self, arr, N):
		ans = 0
		for i in range(1, 1 << N):
			total = 0
			for j in range(N):
				if i & 1 << j:
					total += arr[j]
			if total % 2 == 0:
				ans += 1
		return ans


class Solution:

	def countSumSubsets(self, arr, N):
		powerSet = 1 << N
		ans = 0
		for i in range(powerSet):
			sum = 0
			for j in range(N):
				if i & 1 << j:
					sum += arr[j]
			if sum != 0 and sum % 2 == 0:
				ans += 1
		return ans


class Solution:

	def countSumSubsets(self, arr, N):
		c = 0
		n = 1 << N
		for i in range(1, n):
			s = 0
			for j in range(10):
				if i & 1 << j:
					s += arr[j]
			if not s & 1:
				c += 1
		return c


class Solution:

	def countSumSubsets(self, a, N):
		c = 0
		for i in range(1, 1 << N):
			l = []
			for j in range(N):
				if i & 1 << j:
					l.append(a[j])
			if sum(l) % 2 == 0:
				c += 1
		return c


from itertools import combinations

class Solution:

	def countSumSubsets(self, arr, N):
		ans = 0
		for i in range(1, N + 1):
			for j in combinations(arr, i):
				if sum(j) % 2 == 0:
					ans += 1
		return ans


class Solution:

	def countSumSubsets(self, arr, N):
		count = 0
		for i in range(0, 1 << N):
			s = 0
			for j in range(0, n):
				if i & 1 << j:
					s += arr[j]
			if s % 2 == 0 and s != 0:
				count += 1
			s = 0
		return count


class Solution:

	def countSumSubsets(self, arr, N):
		odd = 0
		even = 0
		a = 0
		b = 0
		for i in arr:
			if i & 1:
				odd += 1
			else:
				even += 1
		a = (1 << even) - 1
		if odd != 0:
			b = (1 << odd - 1) - 1
		return a + b + a * b
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		n = int(input())
		arr = list(map(int, input().strip().split()))
		obj = Solution()
		ans = obj.countSumSubsets(arr, n)
		print(ans)


class Solution:

	def countSumSubsets(self, arr, N):
		count = 0
		for i in range(1, 1 << N):
			temp = 0
			for x in range(N):
				if i >> x & 1:
					temp ^= arr[x]
			if temp & 1 != 1:
				count += 1
		return count


class Solution:

	def countSumSubsets(self, arr, N):
		siz = 1 << N
		count = 0
		for i in range(1, siz):
			binaryStr = self.decimalToBinary(i).zfill(N)
			sum = 0
			for j in range(N):
				if binaryStr[j] == '1':
					sum += arr[j]
			if sum & 1 == 0:
				count += 1
		return count

	def decimalToBinary(self, n):
		return bin(n)[2:]


class Solution:

	def countSumSubsets(self, arr, N):
		c = 0
		for i in range(2 ** len(arr)):
			s = 0
			for j in range(len(arr)):
				if i & 1 << j:
					s += arr[j]
			if s & 1 == 0:
				c += 1
		return c - 1


from itertools import combinations

class Solution:

	def countSumSubsets(self, arr, N):
		l = []
		for i in range(1, N + 1):
			l.extend(combinations(arr, i))
		cont = 0
		for i in l:
			if sum(i) % 2 == 0:
				cont += 1
		return cont


from itertools import combinations

class Solution:

	def countSumSubsets(self, arr, N):
		odds = 0
		for a in arr:
			if a % 2:
				odds += 1
		evens = N - odds
		if odds <= 1:
			return 2 ** evens - 1
		return 2 ** (N - 1) - 1


from itertools import combinations

class Solution:

	def countSumSubsets(self, arr, N):
		p = 0
		for i in range(0, 2 ** N):
			r = []
			for j in range(0, N):
				if i & 1 << j:
					r.append(arr[j])
			if sum(r) % 2 == 0 and r != []:
				p += 1
		return p


from itertools import combinations

class Solution:

	def countSumSubsets(self, arr, N):
		setsize = 2 ** N
		count = 0
		even = []
		for i in range(setsize):
			sumi = 0
			for j in range(N):
				if i & 1 << j > 0:
					sumi += arr[j]
			if sumi % 2 == 0:
				count += 1
		return count - 1


class Solution:

	def countSumSubsets(self, arr, N):
		odds = 0
		for a in arr:
			if a % 2:
				odds += 1
		evens = N - odds
		if odds <= 1:
			return 2 ** evens - 1
		return 2 ** (N - 1) - 1


class Solution:

	def countSumSubsets(self, arr, N):
		setsize = 2 ** N
		count = 0
		even = []
		for i in range(setsize):
			sumi = 0
			for j in range(N):
				if i & 1 << j > 0:
					sumi += arr[j]
			if sumi % 2 == 0:
				count += 1
		return count - 1


class Solution:

	def countSumSubsets(self, arr, N):
		p = 0
		for i in range(0, 2 ** N):
			r = []
			for j in range(0, N):
				if i & 1 << j:
					r.append(arr[j])
			if sum(r) % 2 == 0 and r != []:
				p += 1
		return p