# 2021-Divider
###### tags: `Shopee code league`

(Debuging)

class Solution {
public:
	vector<vector<vector<int>>> allCombinations;
	vector<vector<int>> eachComb;
	vector<int> eachSub;
	int noiseCal(vector<int> vec)
	{
		int noise, sum = 0;
		for (int i = 0; i < vec.size(); i++) {
			sum += vec[i];
		}
		noise = sum * (vec.size() + 1);
		return noise;
	}

	void split(vector<int> &arr, int K, int index, vector<int> eachSub, vector<vector<int>> &eachComb, vector < vector < vector<int>>> &allCombinations)
	{
		if (!eachSub.empty())
		{
			eachComb.push_back(eachSub);
		}

		if (K == 1)
		{
			vector<int> last;
			for (int i = index; i < arr.size(); i++)
			{
				last.push_back(arr[i]);
			}

			if (!last.empty())
			{
				//Backtracking
				eachComb.push_back(last);
				allCombinations.push_back(eachComb);
				eachComb.pop_back();
				return;
			}

		}
		eachSub.clear();
		for (int i = index; i < arr.size(); i++)
		{
			eachSub.push_back(arr[i]);
			split(arr, K - 1, i + 1, eachSub, eachComb, allCombinations);
			if (!eachComb.empty())
			{
				eachComb.pop_back();
			}
		}
	}

	int divide(vector<int> arr, int K, int index, vector<int> eachSub, vector<vector<int>> eachComb, vector < vector < vector<int>>> allCombinations)
	{
		int groupSum = 0;
		int min = INT_MAX;
		split(arr, K, index, eachSub, eachComb, allCombinations);
		printf("Groups = ", allCombinations);

		for (int j = 0; j < allCombinations.size(); j++)
		{
			for (int s = 0; s < allCombinations[j].size(); s++)
			{
				groupSum += noiseCal(allCombinations[j][s]);
			}

			if (groupSum < min)
			{
				min = groupSum;
			}

			groupSum = 0;
		}
		return min;
	}
};

int main() {
	vector<int> arr = { 1,2,3,4,5,6 };
	vector<vector<vector<int>>> allCombinations;
	vector<vector<int>> eachComb;
	vector<int> eachSub;
	int K = 3;
	int index = 0;
	int minimum = 0;
	Solution s;

	minimum = s.divide(arr, K, index, eachSub, eachComb, allCombinations);
	printf("Minimum = ", minimum);

}