### Using pointers to find a subset of size k of a linked list of size n

I am trying to find a subset of a linked list using pointers. I have tried using recursion to do it, but it's not really working.

For example, if I have a linked list of size 5: h -> 1 -> 2 -> 3 -> 4
And I want to find all possible subsets of size 4 with h always being the first node and creating a new linked list every time and storing those lists, how should I do it?

In this case, all the possible subsets would be:
h -> 1 -> 2 -> 3
h -> 1 -> 2 -> 4
h -> 1 -> 3 -> 4
h -> 2 -> 3 -> 4
Well, you could do it purely from the "indices" - either means counting through the linked list each time, or just putting the data into a different container.

 ``123456789101112131415161718192021222324252627`` ``````#include #include using namespace std; int main() { const int MAXIMUM = 4, NUM_REQUIRED = 3; vector< vector > sequences; for ( int i = 1; i <= 9; i++ ) sequences.push_back( { i } ); for ( int n = 2; n <= NUM_REQUIRED; n++ ) { vector< vector > old = sequences; sequences.clear(); for ( const vector &S : old ) { for ( int d = S.back() + 1; d <= MAXIMUM; d++ ) { sequences.push_back( S ); sequences.back().push_back( d ); } } } for ( auto &S : sequences ) { cout << 'h'; for ( int i : S ) cout << " -> " << i; cout << '\n'; } }``````

 ```h -> 1 -> 2 -> 3 h -> 1 -> 2 -> 4 h -> 1 -> 3 -> 4 h -> 2 -> 3 -> 4```
Thank you for your reply! But is there a way I could do it without using vectors? As I haven't learnt vectors yet.
Basically just replace vector with list:

 ``1234567891011121314151617181920212223242526272829303132`` ``````#include #include using namespace std; int main() { constexpr int MAXIMUM {4}, NUM_REQUIRED {3}; list> sequences; for (int i = 1; i <= 9; ++i) sequences.push_back({i}); for (int n = 2; n <= NUM_REQUIRED; ++n) { const auto old {sequences}; sequences.clear(); for (const auto& S : old) for (int d = S.back() + 1; d <= MAXIMUM; ++d) { sequences.push_back(S); sequences.back().push_back(d); } } for (auto& S : sequences) { cout << 'h'; for (int i : S) cout << " -> " << i; cout << '\n'; } }``````

 ``123456789101112131415161718192021222324252627282930`` ``````#include #include using namespace std; int main() { const int NUM_REQUIRED = 4; list original = { 0, 10, 20, 30, 40 }; auto it = original.begin(); // say list< list > sequences = { { *it } }; int left = original.size() - 1; for ( it++; it != original.end(); it++, left-- ) { list< list > added; for ( auto &S : sequences ) { if ( S.size() < NUM_REQUIRED ) { added.push_back( S ); added.back().push_back( *it ); } // sequence WITH element (if possible) if ( S.size() + left > NUM_REQUIRED ) added.push_back( S ); // sequence WITHOUT element (if possible) } sequences = added; } for ( auto &S : sequences ) { for ( auto e : S ) cout << e << " "; cout << '\n'; } }``````

 ```0 10 20 30 0 10 20 40 0 10 30 40 0 20 30 40```
Last edited on
Topic archived. No new replies allowed.