CODEWITHSUNDEEP
pythonalgorithmrecursioncombinationsbacktracking
RocketBug
RocketBug

Reputation: 43

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

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;

I'm having a hard time trying to understand why, "end - i + 1 >= r - index" this condition is needed, I've tried running the code, with and without, it produced the same output, I want to know what is the edge case that causes this condition to return False.

The full code is available here.

Upvotes: 1

Views: 208

Answers (1)

Kyy13
Kyy13

Reputation: 315

Try to group the variables into pieces that are easier to understand e.g.

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

Now we can interpret it like this:

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

so if i is near the end of the given array and there are not enough values left to print a full combination, then the loop (and function) will stop. Let's look at an example:

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.

Upvotes: 1

Related Questions