Zero_combination_sum problem with Sean

bit_vector_solution.py

# TODO: find the problem on LeetCode at the end for optimization





Return an array of numbers that all add up to zero, and there should be no duplicates

[0,1,2,-2,-1,-1,1]

[[1,-1], [-2,2]]    # Each sublist doesn't have to be sorted in a particular way, but they are each unique.   


LEBOWIT

Listen
Example
Brute Force
Optimize
Walkthrough
Implement
Test




# TODO:   Weird type checking at the end


# Brute Force:
Try every possible combination, check whether it sums to zero, and then return the complete, unique set of correct combinations.  
Time complexity:	O(2^n) combinations
Space complexity: O(2^n) combinations


#[1,-1,2]

[False, False, False]
[False, False, True]
[False, True, False]
[False, True, True]
[True, False, False]

#[1,-1]


'''
Bit vector with all possible true and false combinations
  (within a for loop)
    check whether that particular combination adds to zero, if it does, add it to the output
Prune the output for duplicates.   
'''

def to_bit_vector(num):
  bit_vector = []
  while num:
  	bit_vector.append(True if num % 2 == 1 if False)
    num = num // 2   
  return bit_vector
# 0 
# []

def remove_duplicates(collection_):
	seen = set()
  for e in collection_:
    seen.add(e)
  return list(seen)

def listify(tuples_collection):
  out = []
  for tup_ in tuples_collection:
  	out.append(list(tup_))
  return out

'''
# [1,-1,2]

[False, False, False]           []
[False, False, True]
[False, True,  False]
[False, True,  True]
[True,  False, False]
[True,  False, True]
[True,  True,  False]
[True,  True,  True]

'''

def all_zero_combinations(nums):
	n = len(nums)
  # Add one in binary each iteration to generate the next combination.  
	output = []
	curr = 0
  for curr in range(2 ** n):
  	config = to_bit_vector(curr)
  	curr_combo = []
    for i,num in enumerate(nums):
			if config[i]:
      	curr_combo.append(num)
    if len(curr_combo) > 0 and sum(curr_combo) == 0:
    	output.append( tuple( sorted(curr_combo)) )
	return listify( remove_duplicates(output) )