Solution TzWccS3FindTheSum

TzWccS3FindTheSum.java

// Nanadio code sady nanampy commentaire dia niresubmit dia lasa 2eme place :D
// Efa tapitra ny lalao vao ni-resubmit aho an!!

static int closest;
static int closestAbs;
static int target;
static int arrLen;
static int[] nums;

// Ny approche brute force dia manao ny combinaison ana somme rehetra anatin'ilay array
// ary jerena izay somme manakaiky indrindra an'ilay num (target)
// TLE nefa ny brute force tsotra raha vao ngezangeza ilay array moa sendra tafiditra
// eo akaikaikin'ny somme_total / 2 ilay num.

// Noho izany mila mitady fika hanafainganana ilay brute force.
// Ny fika dia sortena descendant aloha ilay array
// Dia jerena ny index mahatonga an'ny prefix sum an'ilay array ho num
// Io index io amin'izay aveo no raisina ho tokony ho isan'ny nombre alaina
// atao somme tao anatin'io array io, ary maka marge index - 3 sy index + 3 mba aha-sur
// fa hita ny "closest" somme amin'ilay num.

static int TzWccS3FindTheSum(int[] numbers, int num) {
    
    closest = numbers[0];
    closestAbs = Integer.MAX_VALUE;
    target = num;
    nums = numbers;
    int arrLen = numbers.length;

    // Sortena dia aveo reverse-na ilay array, mba ahazoana ordre descendant
    Arrays.sort(nums);
    for (int i = 0; i < arrLen / 2; i++) {
        int temp = nums[i];
        nums[i] = nums[arrLen - i - 1];
        nums[arrLen - i - 1] = temp;
    }

    int minTake = 0; // index an'ny prefix sum mandrapatonga any amin'ny num
    int prefSum = nums[minTake++]; // prefix sum
    while (prefSum < target && minTake < arrLen) {
        prefSum += nums[minTake++];
    }

    // raha vao minTake == 1 dia mila atao 1 ny take initial satria tsy afaka maka 0 element
    // fa 1 farafahakeliny
    int lowerLimit = Math.max(minTake - 3, 1);
    int upperLimit = Math.min(minTake + 3, arrLen);
    
    for (int take = lowerLimit; take <= upperLimit; take++) {
        findCombinationSum(new int[take], 0, arrLen - 1, 0, take);
    }

    return closest;
}

static void findCombinationSum(int[] taken, int start, int end, int index, int take) {

    int sum = IntStream.of(taken).sum();
    int abs = Math.abs(target - sum);

    if (index == take) {
        if (abs < closestAbs) {
            closest = sum;
            closestAbs = abs;
        } else if (abs == closestAbs) {
            closest = Math.max(closest, sum);
        }
        return;
    }

    // Raha efa hita ilay target dia ignore-na daholo ny ambiny rehetra mba tsy andaniana fotoana
    if (closest == target) {
        return;
    }

    for (int i = start; i <= end && end - i + 1 >= take - index; i++) {
        taken[index] = nums[i];
        findCombinationSum(taken, i + 1, end, index + 1, take);
    }
}