String combinations in lexicographical order

Problem is to create list of all possible combinations of letters of a given string. If  two strings are with the same set of characters, the lexicographically smallest arrangement of the two strings should appear first. 

For string "abcd" possible combinations would be:

a

ab

abc

abcd

abd

ac

acd

ad

b

bc

bcd

bd

c

cd

d

The code below is the cpp implementation for the problem above.

void print_comb_utils(string str, string tmp, int pos){     for (int i=pos; i < str.size(); i++) {         string tmp2(tmp);         tmp2.push_back(str[i]);         cout << tmp2 << endl;         print_comb_utils(str, tmp2, i+1);     } } void lexi_combs(string str){     for (int i=0 ; i< str.size(); i++) {         cout << str[i] << endl;         string tmp;         tmp.push_back(str[i]);         print_comb_utils(str, tmp, i+1);     } } int main() {     string str;          cin >> str;     lexi_combs(str);     return 0; }

The code just tries to build a recursive structure from the given string. Its assume that the input string has the characters in sorted order else you need to sort the string characters first.

Longest Increasing Subsequence C++ Implementation

Problem is to find the length of the longest increasing sequence from given sequence. We will also print longest sequence, if there are more than one longest sequence with same length we will print one of the sequence.

You can find more details of the problem at wiki: Longest_increasing_subsequence

This is purely my understanding of implementation of longest increasing subsequence DP solution, if you may find it in-efficient please comment.

void LongestIncreasingSubSequence(vector<int> input){     vector<int> storage(input.size());     vector<int> sequence(input.size());          int maxSeq = 0;     for (int i=0; i < input.size(); i++) {         int maxSoFar = 0;         sequence[i] = i;         for (int j = 0; j < i; j++) {             if(input[i] > input[j] && maxSoFar < storage[j]){                 maxSoFar = storage[j];                 sequence[i] = j;             }         }         storage[i] = maxSoFar+1;         if (storage[i] > maxSeq) {             maxSeq = storage[i];         }     }          int i = (int)input.size();     for (; i >= 0; i--) {         if (storage[i] == maxSeq) {             cout << input[i] << " ";             break;         }     }          while (sequence[i] != i) {         cout << input[sequence[i]] << " ";         i = sequence[i];     }     cout << endl;       }

The sequence will be printed in reverse order, you can use stack or temporary storage for printing the sequence in required order.