# 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)
 
 

IyB5b3VyIGNvZGUgZ29lcyBoZXJlCgphbGxfcG9zc2libGVfY29tYmluYXRpb25zID0gW10KZGVmIGdldF9jb21iaW5hdGlvbnMoTiwgZGF0YSwgY3VyX2luZGV4PTAsIGdlbmVyYXRlZF9lbD1bXSwgY2x1c3Rlcl90cmFja2VyPXNldCgpLCBzdWJfZ3JvdXBfdHJhY2tlcj1zZXQoKSk6CglpZiBOID09IDA6CgkJaWYgZ2VuZXJhdGVkX2VsOgoJCQlhbGxfcG9zc2libGVfY29tYmluYXRpb25zLmFwcGVuZCh0dXBsZShnZW5lcmF0ZWRfZWwpKQoJCXJldHVybgoJCglpZiBjdXJfaW5kZXggPj0gbGVuKGRhdGEpOgoJCXJldHVybgoJCglnZXRfY29tYmluYXRpb25zKE4sIGRhdGEsIGN1cl9pbmRleCsxLCBnZW5lcmF0ZWRfZWwsIGNsdXN0ZXJfdHJhY2tlciwgc3ViX2dyb3VwX3RyYWNrZXIpCgkKCWlmIGRhdGFbY3VyX2luZGV4XVsxXSBpbiBjbHVzdGVyX3RyYWNrZXI6CgkJIyBJIGhhdmUgYWxyZWFkeSB0YWtlbiB0aGlzIGNsdXN0ZXIKCQlyZXR1cm4KCQkKCWlmIGRhdGFbY3VyX2luZGV4XVsyXSBpbiBzdWJfZ3JvdXBfdHJhY2tlcjoKCQkjIEkgaGF2ZSBhbHJlYWR5IHRha2VuIHRoaXMgc3ViIGdyb3VwCgkJcmV0dXJuCgkKCWdlbmVyYXRlZF9lbC5hcHBlbmQoZGF0YVtjdXJfaW5kZXhdWzBdKQoJY2x1c3Rlcl90cmFja2VyLmFkZChkYXRhW2N1cl9pbmRleF1bMV0pCglzdWJfZ3JvdXBfdHJhY2tlci5hZGQoZGF0YVtjdXJfaW5kZXhdWzJdKQoJZ2V0X2NvbWJpbmF0aW9ucyhOLTEsIGRhdGEsIGN1cl9pbmRleCsxLCBnZW5lcmF0ZWRfZWwsIGNsdXN0ZXJfdHJhY2tlciwgc3ViX2dyb3VwX3RyYWNrZXIpCQoJZ2VuZXJhdGVkX2VsLnBvcCgpCgljbHVzdGVyX3RyYWNrZXIucmVtb3ZlKGRhdGFbY3VyX2luZGV4XVsxXSkKCXN1Yl9ncm91cF90cmFja2VyLnJlbW92ZShkYXRhW2N1cl9pbmRleF1bMl0pCgkKCXJldHVybgoKCmlmIF9fbmFtZV9fID09ICJfX21haW5fXyI6CglkYXRhID0gWwoJCSgiR0RQX00zIiwgIjEiLCAiR0RQIiksCgkJKCJIUElfTTNfbGcyIiwgIjEiLCAiSFBJIiApLAoJCSgiRkRJX0NfbGc1IiwgIjEiLCAiRkRJIiksCgkJKCJGRElfTTYiLCAiMiIsICJGREkiKSwKCQkoIkV4cG9ydF9NOSIsICIyIiwgIkV4cG9ydCIpLAoJCSgiR0RQX005IiwgIjIiLCAiR0RQIiksCgkJKCJHRFBfTTEyX2xnNyIsICIzIiwgIkdEUCIpLAoJCSgiRXhwb3J0X00xMiIsICIzIiwgIkV4cG9ydCIpCgldCgkKCWdldF9jb21iaW5hdGlvbnMoMywgZGF0YSkKCXByaW50KGFsbF9wb3NzaWJsZV9jb21iaW5hdGlvbnMpCgkKCQkJ