# your code goes here

all_possible_combinations = []
def get_combinations(N, data, cur_index=0, generated_el=[], cluster_tracker=set(), sub_group_tracker=set()):
	if N == 0:
		if generated_el:
			all_possible_combinations.append(tuple(generated_el))
		return
	
	if cur_index >= len(data):
		return
	
	get_combinations(N, data, cur_index+1, generated_el, cluster_tracker, sub_group_tracker)
	
	if data[cur_index][1] in cluster_tracker:
		# I have already taken this cluster
		return
		
	if data[cur_index][2] in sub_group_tracker:
		# I have already taken this sub group
		return
	
	generated_el.append(data[cur_index][0])
	cluster_tracker.add(data[cur_index][1])
	sub_group_tracker.add(data[cur_index][2])
	get_combinations(N-1, data, cur_index+1, generated_el, cluster_tracker, sub_group_tracker)	
	generated_el.pop()
	cluster_tracker.remove(data[cur_index][1])
	sub_group_tracker.remove(data[cur_index][2])
	
	return


if __name__ == "__main__":
	data = [
		("GDP_M3", "1", "GDP"),
		("HPI_M3_lg2", "1", "HPI" ),
		("FDI_C_lg5", "1", "FDI"),
		("FDI_M6", "2", "FDI"),
		("Export_M9", "2", "Export"),
		("GDP_M9", "2", "GDP"),
		("GDP_M12_lg7", "3", "GDP"),
		("Export_M12", "3", "Export")
	]
	
	get_combinations(3, data)
	print(all_possible_combinations)
	
			