CareerCup

Assumptions:
- Result's are sets, meaning a number can occures at most once (e.g. {1,2,3} is a set,
{1,1,2} is not a multi-set, later is not taken into account as valid result)
- The empty set is considered to sum to 0, so there is always at least one solution,
the empty set, which is a valid subset of a set
- I simplify the problem by using a set as input. n = number of elements in the set.

Brute force solution:
- There are 2^n possibilities, which includes the empty set.
- The exponential brute force approach is therefore just testing those options
- The problem is known NP-complete problem
time complexity (2^n), space complexity O(n)

Pseudo polynomial time algo:
- One can construct a solution using two times the knap-sack algorithm
- Lets assume S* is the powerset of the input A and S is a set in that powerset
- If sum(S) = 0, I can say sum(P) = -sum(N), whereas P contains positive element from S
and N the negative once.
- So, If I had a hashmap with all sums possible with all the subsets of A consisting of
only positive numbers and a hashmap with the same for the negative numbers of A. I
could calculate in a linear pass all possible combinations taht will sum to 0
- There is a complication, which is "0" itself, first the set with {0} is a solution,
second, every other combination could always be with 0 element or without.
So If 0 exists in A, it doubles the amount of solutions and adds 1. Therefore I don't
use 0 neither in positive nor negative subsets.

the time and space complexity is
O(n*min(sum(A[i], where A[i] > 0), sum(-A[j], where A[j] < 0)))

Below are both implementations in C++ 11

#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>

using namespace std;

//  --- brute force algo ---
size_t count_subsets_sum0_bf_rec(const unordered_set<int>& input, 
	unordered_set<int>::iterator pos, int sum)
{
	if (pos == input.end()) return sum == 0 ? 1 : 0;
	int value = *pos;
	++pos;
	return count_subsets_sum0_bf_rec(input, pos, sum + value) + 
		count_subsets_sum0_bf_rec(input, pos, sum);
}

size_t count_subsets_sum0_bf(const unordered_set<int>& input)
{
	return count_subsets_sum0_bf_rec(input, input.begin(), 0);
}


//  --- poly time algo ---
unordered_map<int, int> sum_count(const unordered_set<int>& input, int max_sum)
{
	unordered_map<int, int> previous;
	previous[0] = 1;
	for (auto it = input.begin(); it != input.end(); ++it) {
		unordered_map<int, int> current;
		for (auto it2 = previous.begin(); it2 != previous.end(); ++it2) {
			current[it2->first] += it2->second;
			if (it2->first + *it <= max_sum) { // sum is within range
				current[it2->first + *it] += it2->second;
			}
		}
		swap(current, previous);
	}
	return previous;
}

size_t count_subsets_sum0_poly(const unordered_set<int>& input)
{
	int pos_sum = 0, neg_sum = 0;
	unordered_set<int> pos, neg;
	for (int e : input) {
		if (e > 0) {
			pos.insert(e);
			pos_sum += e;
		} else if (e < 0) {
			neg.insert(-e);
			neg_sum -= e;
		}
	}
	int min_sum = min(pos_sum, neg_sum); 
	unordered_map<int, int> pos_sums = sum_count(pos, min_sum);
	unordered_map<int, int> neg_sums = sum_count(neg, min_sum);
	int count = 0; 
	for (auto& ps : pos_sums) {
		if (ps.first == 0) continue;
		auto nsit = neg_sums.find(ps.first);
		if (nsit != neg_sums.end()) {
			count += nsit->second * ps.second;
		}
	}
	if (input.size() != neg.size() + pos.size()) { // contains input a 0-element?
		count = count * 2 + 1; // every already found set that sums to 0 + the 0 element, plus the set consisting of only {0}
	}
	count++; // the empty set
	return count;
}



void test(const unordered_set<int>& input) {
	cout << "test case: {";
	for (int e : input) cout << e << " ";
	cout << "}" << endl;
	int poly = count_subsets_sum0_poly(input);
	cout << "  poly result: " << poly << endl;
	int bf = count_subsets_sum0_bf(input);
	cout << "  brute force result: " << bf << endl << endl;
}

int main()
{
	test({ });
	test({ 0 });
	test({ 0, -1, 1 });
	test({ 0, -1, -2, 1, 2 });
	test({ 0, -1, -2, -3, 1, 2, 3, 4, 5, 6 });
	test({ -1, -2, -3, 1, 2, 3, 4, 5, 6 });
	test({ 0, -1, -2, -4, -6, 1, 2, 3, 4, 5, 6 });
}

think of a binary tree, for each element there're two cases:
1. include the element (left branch)
2. exclude the element (right branch)
use recursion, the runtime is O(2^n)

int Count(vector<int> const &a, unordered_map<uint64_t, int> &memo, int sum = 0, int idx = 0)
{
	if (idx < 0 ||
		idx >= a.size())
	{
		return 0;
	}

	uint64_t memo_key = ((uint64_t)sum << 32) | idx;
	auto it = memo.find(memo_key);
	if (it != memo.end()) {
		return it->second;
	}

	int count = sum + a[idx] == 0 ? 1 : 0;
	count += Count(a, memo, sum + a[idx], idx + 1);
	count += Count(a, memo, sum, idx + 1);

	memo[memo_key] = count;
	return memo[memo_key];
}

#include <iostream>
#include <string>
#include <vector>
using namespace std;


class SubsetSum {
    public:
        int num;
        vector <int> V;
        SubsetSum() {
            num = 0;
        }
        void findNumSubsetSum(int start, int sum);
};

void SubsetSum::findNumSubsetSum(int start, int sum) {
    if (start >= V.size()) {
        return ;
    }
    if(V[start] == sum) {
        num++;
        return;
    }
    findNumSubsetSum(start + 1, sum - V[start]);
    findNumSubsetSum(start + 1, sum);
}



int main() {
    SubsetSum S;
    S.V.push_back(2);
    S.V.push_back(-2);
    S.V.push_back(1);
    S.V.push_back(4);
    S.V.push_back(5);
    S.V.push_back(-8);

    S.findNumSubsetSum(0, 0);
    cout << "Number of Sum :"<<S.num <<"\n";

}

static int CountOfPairsThatSumIsZero(int[] list)
	{
		var res = new Dictionary<int, int>();
		var map = new Dictionary<int, int>(list.Length);
		
		foreach (var a in list)
		{
			map.Add(a, 1);
		}
		foreach (var a in list)
		{
			if (map.ContainsKey(-a))
			{
				if (!res.ContainsKey(-a))
				{
					res.Add(a, 1);
				}
			}
		}
		return res.Count;
	}

public static void main(String[] args) {
		//recursion approach
		int[] arr = { 1, -1, 2, -2 };
		List<List<Integer>> list = new ArrayList<>();
		subsetzero(arr, 0, 0, 0, list, new ArrayList<>());
		System.out.println("->" + list.size());

		//dp approach
		int m = count(arr);
		System.out.println("-->"+m);

	}

	public static int count(int[] arr) {
		int n = arr.length - 1;
		sort(arr, 0, n);
		int posind = posindex(arr, 0, n);

		int negsum = 0;
		for (int i = 0; i < posind; i++)
			negsum += arr[i];

		int possum = 0;
		for (int i = posind; i <= n; i++)
			possum += arr[i];

		negsum = Math.abs(negsum);
		int[][] negdp = new int[negsum + 1][posind + 1];
		for (int p = 0; p <= negsum; p++) {
			for (int q = 1; q <= posind; q++) {
				int pov = Math.abs(arr[q - 1]);
				negdp[p][q] = negdp[p][q - 1];
				if (p == pov)
					negdp[p][q] += 1;
				else if (p >= pov && p - pov <= negsum)
					negdp[p][q] = Math.max(negdp[p][q - 1], negdp[p - pov][q - 1]);
			}
		}

		int[][] posdp = new int[possum + 1][n - posind + 2];
		for (int p = 0; p <= possum; p++) {
			for (int q = 1; q <= n - posind + 1; q++) {
				posdp[p][q] = posdp[p][q - 1];
				if (p == arr[q + posind - 1])
					posdp[p][q] += 1;
				else if (p >= arr[q + posind - 1] && p - arr[q + posind - 1] <= possum)
					posdp[p][q] = Math.max(posdp[p][q - 1], posdp[p - arr[q + posind - 1]][q - 1]);
			}
		}

		int count = 0;
		if (negsum > possum) {
			while (negsum >= 0) {
				if (posdp[negsum][n - posind] > 0)
					count += Math.min(negdp[negsum][posind], posdp[negsum][n - posind +1]);
				negsum--;
			}
		} else {
			while (possum >= 0) {
				if (negdp[possum][posind] > 0)
					count += Math.min(posdp[possum][n - posind +1], negdp[possum][posind]);
				possum--;
			}
		}
		return count;
	}

	public static int posindex(int[] arr, int l, int h) {
		if (l >= h)
			return -1;
		while (l < h) {
			int mid = (h - l) / 2 + l;
			if (mid - 1 >= 0 && arr[mid] >= 0 && arr[mid - 1] < 0)
				return mid;
			else if (mid - 1 >= 0 && arr[mid] < 0 && arr[mid - 1] < 0)
				l = mid + 1;
			else if (mid - 1 >= 0 && arr[mid] > 0 && arr[mid - 1] > 0)
				h = mid - 1;
		}
		return -1;
	}

	public static void sort(int[] arr, int l, int h) {
		int i = l;
		int j = h;
		int mid = arr[(h - l) / 2 + l];
		while (i <= j) {
			while (arr[i] < mid)
				i++;
			while (arr[j] > mid)
				j--;
			if (i <= j) {
				swap(arr, i, j);
				i++;
				j--;
			}
		}
		if (l < j)
			sort(arr, l, j);
		if (i < h)
			sort(arr, i, h);
	}
	
	public static void swap(int[] arr, int i, int j) {
		int t = arr[i];
		arr[i] = arr[j];
		arr[j] = t;
	}

	//1, -1, 2, -2
	//[-2, -1, 1, 2]
	public static void subsetzero(int[] arr, int sum, int k, int count, List<List<Integer>> list, List<Integer> li) {
		if (sum == 0 && li.size() > 0 && !list.contains(li)){
			count = count + 1;
			list.add(new ArrayList<>(li));
		}
		
		if (k > arr.length - 1)
			return;
		
		li.add(arr[k]);
		subsetzero(arr, sum + arr[k], k + 1, count, list, li);
		li.remove(new Integer(arr[k]));
		subsetzero(arr, sum, k + 1, count, list, li);
	}

from itertools import combinations, chain #unlock python wealth
def powerset(arr):
    return list (chain.from_iterable(combinations(arr, r) for r in range(len(arr)+1)))

def count (l):
    print (l)
    totals= [sum (tup) for tup in l]
    print (totals)
    return len ([t for t in totals if t ==0] )

a= [-1,-2,1,2,0]
print (f'total subsets for set {a} that sum to 0: {count (powerset(a))}')

$Zeros = 0;
$Subsets = array_map('intval', explode(',', $_REQUEST['i']??''));

$Compliments = [];

foreach ($Subsets as $i => $Number) {
	$Compliment = -$Number;

	if (isset($Compliments[$Compliment]) && $Compliments[$Compliment] !== $i) {
		$Zeros++;
		echo "$Number,$Compliment\n";
	}

	if (!isset($Compliments[$Compliment])) {
		$Compliments[$Number] = $i;
	}
}

echo $Zeros;

Python solution: O(n)

# Code to get -->
# a. All possible subsets of a given list
# b. All possible subsets/no of subsets of a given list whose sum is equals to target number 
# c. All possible subsets/no of subsets of a given list whose sum is equals to 0
# Recursive approach

def powerset(arr):
    x=[]
    l = len(arr)
    s = ['']*len(arr)
    helper(arr,s,0,x)
    #print(x)
    
    # Looping through the subsets to find target number
    cnt = 0
    for i in x:
        if sum(i) == 0 and len(i) != 0:
            cnt +=1
            #print subsets that corresponds to target number
            print(i)
    # print no of subsets that corresponds to target number
    print(cnt) 
    
def helper(arr,s,n,x):
    if n == len(arr):
        temp =[]
        for i in s:
            if i != '':
                temp.append(i)
        x.append(temp)        
        #print(x)
    else:
        s[n] = ''
        helper(arr,s,n+1,x)
        s[n] = arr[n]
        helper(arr,s,n+1,x)

powerset([-1,-2,1,2,0])