Program to print all subset of length l

Question

#include<iostream>
using namespace std;
void combinationUtil(int arr[], int n, int r, int index, int data[], int i);
void printCombination(int arr[], int n, int r)
{
    int data[r];
    combinationUtil(arr, n, r, 0, data, 0);
}
void combinationUtil(int arr[], int n, int r, int index, int data[], int i)
{
    if (index == r)
    {
        for (int j = 0; j < r; j++)
            cout << data[j] << " ";
        cout << endl;
        return;
    }
    if (i >= n)
        return;
    data[index] = arr[i];
    combinationUtil(arr, n, r, index + 1, data, i + 1);
    combinationUtil(arr, n, r, index, data, i + 1);
}
int main()
{
    int n = 5;
    int arr[n] = { 1, 2, 3, 4, 5 };
    int k = 3;
    printCombination(arr, n, k);
    return 0;
}

This is the code to print all possible subsets of length k. I didn’t understand the part how the function returns to the part where it prints the subset 134 after printing the subset 125. Please explain. I even drew the tree, but how does the code create that "13" series after printing 125 . I'm quite weak at recursion, please correct me if there's a mistake in my code or tree.

Recursion Tree:

"the part where it prints the subset 134 after printing the subset 125": what part is that? — Scott Hunter, Jul 18 '20 at 15:42
Can you explain what the various parameters to `combinationUtil` represent? — Scott Hunter, Jul 18 '20 at 15:43
You've drawn the recursion tree and you are getting on paper what you get on the screen. What's the problem then? Do you've confusion on how you drew that tree? — brc-dd, Jul 18 '20 at 15:46
@ScottHunter `arr[]` ---> Input Array | `n` ---> Size of input array | `r ` ---> Size of a combination to be printed | `index` ---> Current index in `data[]` | `data[]` ---> Temporary array to store current combination | `i` ---> index of current element in `arr[]` :) — brc-dd, Jul 18 '20 at 15:49
[OT]: `int data[r]` is invalid C++ with not compile time `r`. (VLA extension). — Jarod42, Jul 18 '20 at 15:50
Try to write down the callstack and the states of the local variables as you traverse the tree you've drawn. Can you see the difference in how your calls are working out and how you've drawn your tree? I.e. the tree you've drawn is not how your code executes (hint: you will only ever have two children per inner node in your calling structure yet you've drawn a tree with up to three children per node). — BeyelerStudios, Jul 18 '20 at 15:51
My doubt is how does the code come to '13' series after printing all the '12' series(123,124,125) @ScottHunter — Vinayaka Dayanand, Jul 18 '20 at 15:58
@BeyelerStudios can you please provide the tree on how my code works? — Vinayaka Dayanand, Jul 18 '20 at 16:01
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5910058) — Jesper Juhl, Jul 18 '20 at 16:14
Does this answer your question? [How to create a permutation in c++ using STL for number of places lower than the total length](https://stackoverflow.com/questions/61392431/how-to-create-a-permutation-in-c-using-stl-for-number-of-places-lower-than-the) — kesarling He-Him, Jul 18 '20 at 17:02

score 0 · Answer 1 · answered Jul 18 '20 at 17:09

Your code is an example of DFS (Depth First Search). For every node, it first recurs on the leftmost child, then when it's at the rightmost child, this "part" of the function ends, essentially going back to the previous node and recurring on its children. Basically, children have priority over siblings, and left has priority over right.

If any part of this post is unclear, tell me and I will elaborate. Welcome to Stack Overflow :)

BeyelerStudios · Accepted Answer · 2020-07-19T20:01:29.123

Let's inspect the programme execution (you can do this easily using a debugger).

Firstly since arr, n and r don't change in the call tree, let's note them down first:

n := 5, r := 3, arr := {1, 2, 3, 4, 5}

For the variable arguments let's build a table and note the first call to combinationUtil:

Callstack             | index | i     | data      | Cases (printing, returning or recursing)
----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 0     | 0     | {., ., .} | recursing (index != r, i != n)
  printCombination    |       |       |           |
  main                |       |       |           |

Let's ignore main and printCombination in the future, but note that the top of the stack describes the function we've just entered with the given state of index, i and data (and arr, n, r but those won't change) - specifically we did not yet execute any of the body of the function like assigning data[index] = arr[i] or similar. Following the execution note how we're neither printing nor breaking out early since index != r and i != n meaning we'll recurse twice in this function call. Let's step to the first recursive call:

----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 1     | 1     | {1, ., .} | recursing
  combinationUtil     | 0     | 0     |           |

When we enter our first recursive call, 1 will have been written to data so at the beginning of the function we can now see this value in data. We'll continue twice:

----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 2     | 2     | {1, 2, .} | recursing
  combinationUtil     | 1     | 1     |           |
  combinationUtil     | 0     | 0     |           |
----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 3     | 3     | {1, 2, 3} | printing (index == r)
  combinationUtil     | 2     | 2     |           |
  combinationUtil     | 1     | 1     |           |
  combinationUtil     | 0     | 0     |           |

New case: index == r i.e. we'll loop over data, print its current content and return, one level higher we'll step into the next recursive call so let's look at the next steps:

----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 2     | 3     | {1, 2, 3} | recursing
  combinationUtil     | 2     | 2     |           |
  combinationUtil     | 1     | 1     |           |
  combinationUtil     | 0     | 0     |           |
----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 3     | 4     | {1, 2, 4} | printing
  combinationUtil     | 2     | 3     |           |
  combinationUtil     | 2     | 2     |           |
  combinationUtil     | 1     | 1     |           |
  combinationUtil     | 0     | 0     |           |
----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 2     | 4     | {1, 2, 4} | recursing
  combinationUtil     | 2     | 3     |           |
  combinationUtil     | 2     | 2     |           |
  combinationUtil     | 1     | 1     |           |
  combinationUtil     | 0     | 0     |           |
----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 3     | 5     | {1, 2, 5} | printing
  combinationUtil     | 2     | 4     |           |
  combinationUtil     | 2     | 3     |           |
  combinationUtil     | 2     | 2     |           |
  combinationUtil     | 1     | 1     |           |
  combinationUtil     | 0     | 0     |           |
----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 2     | 5     | {1, 2, 5} | returning (i >= n)
  combinationUtil     | 2     | 4     |           |
  combinationUtil     | 2     | 3     |           |
  combinationUtil     | 2     | 2     |           |
  combinationUtil     | 1     | 1     |           |
  combinationUtil     | 0     | 0     |           |

Can you see how deep the call stack got until we printed 125? If you've been drawing the call graph along you should have something along the following now:

        [] (0, 0)
       /
      1 (1, 1)
     /
   12 (2, 2)
  /  \
123   12 (2, 3)
     /  \
    124  12 (2, 4)
        /  \
      125  ret (2, 5)

We're currently at ret and I've marked the arguments (index, i) from our current callstack along the root path (from [] to ret). We'll be returing in ret because i == n, we'll then return from each call up the tree until we reach 1 (index=1, i=1) where we return from its first recursion (index+1, i+1) so its next is (index, i+1) and the following next 6 steps together look like:

----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 1     | 2     | {1, 2, 5} | recursing
  combinationUtil     | 1     | 1     |           |
  combinationUtil     | 0     | 0     |           |
----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 2     | 3     | {1, 3, 5} | recursing
  combinationUtil     | 1     | 2     |           |
  combinationUtil     | 1     | 1     |           |
  combinationUtil     | 0     | 0     |           |
----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 3     | 4     | {1, 3, 4} | printing
  combinationUtil     | 2     | 3     |           |
  combinationUtil     | 1     | 2     |           |
  combinationUtil     | 1     | 1     |           |
  combinationUtil     | 0     | 0     |           |
----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 2     | 4     | {1, 3, 4} | recursing
  combinationUtil     | 2     | 3     |           |
  combinationUtil     | 1     | 2     |           |
  combinationUtil     | 1     | 1     |           |
  combinationUtil     | 0     | 0     |           |
----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 3     | 5     | {1, 3, 5} | printing
  combinationUtil     | 2     | 4     |           |
  combinationUtil     | 2     | 3     |           |
  combinationUtil     | 1     | 2     |           |
  combinationUtil     | 1     | 1     |           |
  combinationUtil     | 0     | 0     |           |
----------------------+-------+-------+-----------+------------------------------------
> combinationUtil     | 2     | 5     | {1, 3, 5} | returning
  combinationUtil     | 2     | 4     |           |
  combinationUtil     | 2     | 3     |           |
  combinationUtil     | 1     | 2     |           |
  combinationUtil     | 1     | 1     |           |
  combinationUtil     | 0     | 0     |           |

And the call graph up to this point looks like:

               [] (0, 0)
              /
             1 (1, 1)
     /-------^-------\
   12                 1 (1, 2)
  /  \               /
123   12           13 (2, 3)
     /  \         /  \
    124  12     134   13 (2, 4)
        /  \         /  \
      125  ret     135  ret (2, 5)

``` [] (0, 0) / 1 (1, 2) / \ 13 (2, 3) / \ 134 13 (2, 4) / \ 135 ret (2, 5) ``` @BeylerStudios — Vinayaka Dayanand, Jul 18 '20 at 20:01
+1 @VinayakaDayanand almost, you only missed the `1 (1, 1)` between `[] (0, 0)` and `1 (1, 2)`, I'll update my answer now. — BeyelerStudios, Jul 19 '20 at 20:01

Program to print all subset of length l

2 Answers2