Dana jest tablica typu tab=array[1..n] of integer. Proszę napisać funkcję, która znajdzie najmniejszy (w sensie liczebności) podzbiór elementów tablicy, dla którego suma elementów jest równa sumie indeksów tych elementów. Do funkcji należy przekazać tablicę, funkcja powinna zwrócić sumę elementów znalezionego podzbioru. Na przykład dla tablicy: …

sum_of_indexes_values.cpp

#include <cstdio>
#include <algorithm>

using namespace std;

void probuj_tak(int values, int indexes, int pos, int chosen, int* minimal_chosen_value, int* minimal_chosen, int arr[], int array_length)
{
    if(pos == array_length) // Jeśli doszliśmy do końca tablicy
    {
        if(values == indexes && chosen > 0 && values > 0) // a nasz podzbiór spełnia warunki zadania (values > 0, bo zabezpieczamy się przed cwanym wybraniem tylko nicnieznaczącego zera)
        {
            printf("Match for values = indexes = %d, %d chosen\n",values,chosen);
            if(*minimal_chosen > chosen) // oraz wybraliśmy mniej liczb niż kiedykolwiek
            {
                *minimal_chosen = chosen; // zapisujemy ile liczb udało nam się wybrać
                *minimal_chosen_value = values; // zapisujemy sumę podzbioru
            }
        }
        return;
    }
    else
    {
        probuj_tak(values, indexes, pos+1, chosen,minimal_chosen_value,minimal_chosen,arr, array_length); // Sprawdzam co by było, gdybym nie brał aktualnego elementu
        probuj_tak(values+(arr[pos]), indexes + pos, pos+1, chosen+1,minimal_chosen_value,minimal_chosen,arr, array_length); // Sprawdzam co by było, gdybym wziął aktualny element
    }
}

int minimal_chosen(int arr[], int array_length)
{
    int minimal_chosen = array_length+1; // Na pewno więcej niż długość tablicy nie wybierzemy
    int minimal_chosen_value = 0; // Byle co, to używamy jako zmienną do zwracania
    probuj_tak(0,0,0,0,&minimal_chosen_value, &minimal_chosen,arr, array_length);
    return minimal_chosen_value; // Zwracamy co funkcja zwróciła
}

int main()
{
    int arr[] = {0,7, 3, 5, 11, 2};
    int array_length = 6;
    
    printf("%d\n",minimal_chosen(arr, array_length));
    
    return 0;
}