Sinux's blog

By Sinux, history, 4 months ago, In English

void search(int k) { if (k == n) { // process subset } else { search(k+1); subset.push_back(k); search(k+1); subset.pop_back(); } }

I am having a really hard time understand this code. I especially don't understand how 'k' turns to 2 after 'k' reaches 3. I don't understand because there's no such code that does search(k-1) but it backtracks automatically. I think It's related to the thing backtracking. Someone plz help!!!

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

It's building subset from $$$1$$$ to $$$n$$$. For each element, you can decide: to include it or not? Its like a DFS.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am very noob to this CP so I don't know what DFS is.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Should I just memorize that k backtracks to the previous condition or try to understand?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    bro doesn't understand the idea of simple recursion you're referencing that to dfs?

    it's like you try to teach thesigma function using integrals to a 7th grader

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

This code generating all unique ({1,2,3} and {3,2,1} are same) subsets from 1 to n. There are two options, to add element or left it and transit with k+1, which generate all subset with size 1 till n.

About why k become 2 from 3, just because it go with first possible way. If this is too difficult to you, I recomment you to read this and watch here Good luck!

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But I don't understand how the 'k' turns to 2 after reaching 3. There is no such a line that minuses k but I don't understand how this backtracks automatically.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      At first you shall learn dfs with graph theory, and watch in youtube how works recursiohn,after this it will be understandable, hope i helped you!

»
4 months ago, # |
Rev. 5   Vote: I like it +1 Vote: I do not like it

it doesn't return to, it's another stack of recursions

this code works as follows:

either an element comes or doesn't, in the else part, it handles when we haven't visited every element, the first 2 lines of the else part are when it comes, and the second 2 lines are when it doesn't.
bcuz of the way recursion(in total stack memory) works, it starts drawing it from above, not equally everywhere, so it first finishes writing 123, then goes to the last time it got branched and solves there etc

it's just understanding recursions
imagine you say to your friend, hey go put this box there, then come back, the other box here, he goes to put that box there, but when he does he sees another friend who tells him the same thing, and he goes and puts the box in the place the other friend tells him, and since there isn't anyone telling him to go do another thing, he returns to the second friend and moves the other box, then he returns to you and moves the other box, why? cause you told it to, not now but before, it's the same

the function get's called on k = 2 here, he goes and does the job but another friend calls him on k = 3 now and he goes and does his job and another friend on k = 4, each friend is giving him 2 tasks, when he does the first task of the k = 4, no one tells him to go do something, so he returns and does the second tasks of k = 4 and then he goes to do the second task of k = 3 and goes to do the second task of k = 2, he remembers each task, and does them in a last in first out order, which causes this going back to action

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So the 'k' will reach 4 but it returns nothing so nothing happens when k reaches 4. Am I right?

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      when k reaches for and it does the job, and there is no task(no other element in the initial array to use for the subset) it ends this single process, and goes to the last process he remembers

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah but I don't understand why it backtracks automatically even though I didn't write a single line of code to minus k. This recursion is so different than the recursion problems such as fibonacci numbers. Sorry for the slow understanding.

        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          it's not the same k man, they are different copies of each other,

          I call 2 persons, I tell them do this job with k = 4, I tell the other one: do this job with k = 1, but wait for the other one to finishes, when the first guy finished, the second dude starts with a different k, the other k didn't backtrack to 1, it's another one

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            So there are multiple k's?

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              yes

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                How? the parameter is only one integer.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  it's the way memory works in c++