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

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" 这个条件是必需的，我试过运行代码，有和没有，它产生相同的输出，我想知道导致这种情况 return 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.

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

I'm trying to understand how to print all the possible combinations of a array

python

algorithm

recursion

combinations

backtracking