我试图理解如何打印数组的所有可能组合

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

The full code is available here.

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，并且没有足够的值来打印完整的组合，那么循环（和函数）将停止。让我们看一个例子：

Given

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

The top level function will start to form a combination with 1 and then with 2 resulting in (1,2,3), (1,2,4), (1,3,4)

It will not try 3 and 4, because (values_left_in_array < values_left_to_print).

If the condition was not there, then the function would try 3 and 4, but the values in the sequence only ever increase in index from left-to-right in the given array, so the combination will end because i will reach end before being able to find 3 values.