printing all increasing subsequence using recursion

Question

I'm trying to print all increasing subsequence with following. But it is not working accordingly.

Please explain what actually my code doing.

I'm stuck since last 1 week. But unable to figure out.

#include <bits/stdc++.h>

using namespace std;

int temp[1000];
int ans = 1;
int cnt  = 0;

void solve(int *arr, int n, int k)
{
    if(k == n){
        cnt++;
        for(int j = 0; j < n; j++){
            cout<<temp[j]<<" ";
        }

        cout<<endl;
        return;
    }

    for(int i = k; i < n; ++i){
        if(arr[k] <= arr[i]){
            temp[k] = -2;
            solve(arr, n, i+1);
            temp[k] = 2;
        }
    }
}

int main()
{
    int arr[] = {4, 1, 13, 7, 0, 2, 8, 11, 3};
    //int arr[] = {-1, 1 ,2, 3, 4};
    //int arr[] = {-1,1,2,3,4,11, 5,6, 2, 9};

    memset(temp, -1, sizeof(temp));

    solve(arr, 9, 0);
    cout<<cnt<<endl;

    return 0;
}

Output should be total number of enumerating increasing subsequence.

You sure you need all? For example `[1, 2, 3]` would give `[[1], [2], [3], [1, 2], [2, 3], [1, 2, 3]`. Or only ones that are not part of other subsequences? — krisz, Aug 15 '19 at 16:33
See this lovely [debug](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) blog for help. — Prune, Aug 15 '19 at 16:41
Welcome to StackOverflow. Please read and follow the posting guidelines in the help documentation, as suggested when you created this account. [Minimal, complete, verifiable example](https://stackoverflow.com/help/minimal-reproducible-example) applies here. We cannot effectively help you until you post your MCVE code and accurately specify the problem. We should be able to paste your posted code into a text file and reproduce the problem you specified. "It is not working" is not a problem specification. — Prune, Aug 15 '19 at 16:41
When you update your post, include the output traces of intermediate values, and your opinions on where it begins to fail and how. Include the expected and actual results. — Prune, Aug 15 '19 at 16:45
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5910058) — Jesper Juhl, Aug 15 '19 at 16:47

krisz · Accepted Answer · 2019-08-16T15:23:59.937

This prints all increasing subsequences:

void print(const vector<int> v) {
  for (size_t i = 0; i < v.size() - 1; ++i)
    cout << v[i] << ", ";
  cout << v.back() << endl;
}

int solve(const vector<int>& v, size_t start, vector<int>& sequence) {
  print(sequence);
  int count = 1;
  for (size_t i = start; i < v.size(); ++i) {
    if (v[i] >= sequence.back()) {
      sequence.push_back(v[i]);
      count += solve(v, i + 1, sequence);
      sequence.pop_back();
    }
  }
  return count;
}

size_t solve(const vector<int>& v) {
  int count = 0;
  for (size_t i = 0; i < v.size(); ++i) {
    vector<int> sequence{v[i]};
    count += solve(v, i + 1, sequence);
  }  
  return count;
}

Usage:

vector<int> v{4, 1, 13, 7, 0, 2, 8, 11, 3};
auto count = solve(v);
cout << "Count: " << count << endl;

Output:

4
4, 13
4, 7
4, 7, 8
4, 7, 8, 11
4, 7, 11
4, 8
4, 8, 11
4, 11
1
1, 13
1, 7
1, 7, 8
1, 7, 8, 11
1, 7, 11
1, 2
1, 2, 8
1, 2, 8, 11
1, 2, 11
1, 2, 3
1, 8
1, 8, 11
1, 11
1, 3
13
7
7, 8
7, 8, 11
7, 11
0
0, 2
0, 2, 8
0, 2, 8, 11
0, 2, 11
0, 2, 3
0, 8
0, 8, 11
0, 11
0, 3
2
2, 8
2, 8, 11
2, 11
2, 3
8
8, 11
11
3
Count: 48

can i add arbitrary node at v[0] = INT_MIN and calling solve(v, 0 , sequence) from main with following modification for (size_t i = start; i < v.size(); ++i) { if (v[i] >= sequence.back()) { sequence.push_back(v[i+1]); count += solve(v, i + 1, sequence); sequence.pop_back(); } } — rajuugupta, Aug 16 '19 at 18:14
That would break stuff. You could add a `start` parameter to `solve(const vector&)` or modify it to take a pair of iterators. — krisz, Aug 16 '19 at 18:30

printing all increasing subsequence using recursion

1 Answers1