Unique Combinations

This algorithm finds all unique combinations in a specified list of values.



									/*****Please include following header files*****/
// stdlib.h
/***********************************************/

typedef struct {
	char** Combination;
	int CombinationSize;
} Combination;

typedef struct {
	Combination* Combinations;
	int TotalCombinations;
} Combinations;

char** AddItemInArray(char** arr, int arrSize, char* item) {
	char** newArr = (char**)malloc(sizeof(char*) * (arrSize + 1));

	for (int i = 0; i < arrSize; ++i) {
		newArr[i] = arr[i];
	}

	newArr[arrSize] = item;

	return newArr;
}

Combinations AddCombination(Combinations combinations, Combination item) {
	Combination* newCombinations = (Combination*)malloc(sizeof(Combination) * (combinations.TotalCombinations + 1));

	for (int i = 0; i < combinations.TotalCombinations; ++i) {
		newCombinations[i] = combinations.Combinations[i];
	}

	newCombinations[combinations.TotalCombinations] = item;
	combinations.Combinations = newCombinations;
	++combinations.TotalCombinations;

	return combinations;
}

Combinations GenerateCombinations(char** arr, int arrLength)
{
	int length = arrLength;
	Combinations combinations;
	combinations.Combinations = (Combination*)malloc(sizeof(Combination));
	combinations.TotalCombinations = 0;

	for (int i = 0; i < (1 << length); ++i)
	{
		Combination combination;
		combination.Combination = (char**)malloc(sizeof(char*));
		combination.CombinationSize = 0;
		int count = 0;

		for (count = 0; count < length; ++count)
		{
			if ((i & 1 << count) > 0)
				combination.Combination = AddItemInArray(combination.Combination, combination.CombinationSize++, arr[count]);
		}

		if (count > 0 && combination.CombinationSize > 0)
			combinations = AddCombination(combinations, combination);
	}

	return combinations;
}
								


Example

									char* arr[] = { "How", "Are", "You" };
Combinations combinations = GenerateCombinations(arr, 3);
								


Output

									{"How"}
{"Are"}
{"How", "Are"}
{"You"}
{"How", "You"}
{"Are", "You"}
{"How", "Are", "You"}