Я пытаюсь понять, как распечатать все возможные комбинации массива

Question

i = start; 
while(i <= end and end - i + 1 >= r - index): 
    data[index] = arr[i]; 
    combinationUtil(arr, data, i + 1, 
                    end, index + 1, r); 
    i += 1; 

Мне трудно понять, почему, "end - i + 1> = r - index", это условие необходимо, я попытался запустить код, с и без, он произвел тот же вывод, я хочу знать, что такое крайний случай, который заставляет это условие возвращать False.

Полный код доступен здесь.

Answer 1

Попробуйте сгруппировать переменные в части, которые легче понять, например,

int values_left_to_print = r - index; // (size of combination to be printed) - (current index into data)
int values_left_in_array = end - i + 1; // number of values left until the end of given arr

Теперь мы можем интерпретировать это следующим образом:

for (int i = start; i <= end && (values_left_in_array >= values_left_to_print); i++)  
{

, так что если i около end данного массива, и для печати полной комбинации осталось недостаточно значений, тогда l oop (и функция) остановится. Давайте рассмотрим пример:

Учитывая

arr = {1,2,3,4}
n = 4; // size of arr
r = 3; // size of combination

Функция верхнего уровня начнет формировать комбинацию с 1, а затем с 2, в результате чего (1,2,3) , (1,2,4), (1,3,4)

Он не будет пытаться 3 и 4, потому что (values_left_in_array < values_left_to_print).

Если условия не было, то Функция будет пытаться использовать 3 и 4, но значения в последовательности только увеличиваются в индексе слева направо в данном массиве, поэтому комбинация закончится, потому что i достигнет end, прежде чем сможет найти 3 значения .