input: [1, 2, 3, 4, 5],  n = 3
output: [[[5],[1,4],[2,3]];

**
 * In this solution we use backtracking to find every possible combination of buckets to fill and then for each possible solution we calculate its varience and hold onto the smallest variance to return
 * 
 * Time complexity: O(n*k^n)
 *  We follow every possible path and compare its varience. For N numbers in arr there are k possible buckets it could placed into thus there are k^N possible cases to explore. In each branch we check iterate n times so time complexity is O(n*k^n)
 * Space Complexity: let p be the space used per used recursive call. We would make in total k^n calls so the space complexity is O(p*k^n)
 */
function backtrackingSolution(arr, k){
    const result = 
    Array.from({length: k}, () => [] ), 
    seen = [], 
    totalSum = arr.reduce((prev, curr) => prev + curr, 0), 
    avg = Math.floor(totalSum / k);
    
    const calculateVarience = () => {
        let ss = 0;
        result.forEach(bucket => {
          const difference = avg - bucket.reduce((p,c) => p + c, 0);
          ss += difference**2
        });
        return ss/k;
      }

    let smallestVarience = Infinity, bestBucketCopy = null, 
    valuesAdded = 0;

    const backtrack = (index) => {
      if (valuesAdded === arr.length) {
        const currentVarience = calculateVarience();
        if (currentVarience < smallestVarience){
          smallestVarience = currentVarience;
          bestBucketCopy = result.map(a => a.map(b => b));
        }
        return;
      };
      for (let i = index; i < arr.length; i++){
        if (!seen[i]){
          seen[i] = true;
          for (let j = 0; j < k; j++){
            result[j].push(arr[i]);
            valuesAdded++;
            backtrack(i+1);
            result[j].pop();
            valuesAdded--;
          }
          seen[i] = false;
        }
      }
    }
    backtrack(0);
    return bestBucketCopy;
}