1. Next Permutation 2. Unique Binary Search Trees 3. Recover Binary Search Tree 4. Subsets 题目描述参见LeetCode http://leetcode.com/onlinejudge

Unique Binary Search Trees.cc

int numTrees(int n) {
    vector<int> dp(n+1, 0);
    dp[0] = dp[1] = 1;
    for(int i=2;i<=n;i++) {
        //there will be one value at the root, with whatever remains 
        // on the left and right each forming their own subtrees. 
        // Iterate through all the values that could be the root... 
        for(int j=0;j<i;j++) {
            dp[i] += dp[j] * dp[i-j-1];
        } 
    }
    return dp[n];
}

Next Permutation.cc

void nextPermutation(vector<int> &num) {
    int N = num.size();
    for(int i=N-1;i>0;i--) {
        if(num[i] > num[i-1]) { //reverse find the first num larger than it's prev
            int j;
            for(j=N-1;j>=i;j--) { //reverse find the first num larger than pivot
                if(num[j] > num[i-1]) {
                    break;
                }
            }
            swap(num[j],num[i-1]);
            reverse(num.begin()+i,num.end());
            return;
        } 
    }
    reverse(num.begin(),num.end());
}

Recover Binary Search Tree.cc

/*
1. Use Morris method to inorder travel tree 
1. find the first pair <last,curr> that curr is smaller than last
1. than find the second pair <last,curr> that curr is smaller than last
1. swap the first pair's first and the second pair's second TreeNode, the tree is recoverd
    1. if there is only one pair, swap the first pair's first and second node
*/
void recoverTree(TreeNode *root) {
    TreeNode *last, *first, *second;
    last = first = second = NULL;
    while(root) {
        if(root->left) {
            TreeNode* p = root->left;
            while(p->right != NULL && p->right != root) {
                p = p->right;
            }
            if(p->right == root) {
                if(last && root->val < last->val) {
                    first = first ? first : last;
                    second = root;
                }
                last = root;

                p->right = NULL;
                root = root->right;
            }else {
                p->right = root;
                root = root->left;
            }
        }else {
            if(last && root->val < last->val) {
                first = first ? first : last;
                second = root;
            }
            last = root;

            root = root->right;
        }
    } 
    if(first && second) {
        swap(first->val, second->val);
    }
    return;
}

Subsets.cc

vector<vector<int> > subsets(vector<int> &s) {
    vector<vector<int> > ans;
    sort(s.begin(),s.end());
    int N = pow(2,s.size());
    for(int i=0;i<N;i++) {
        vector<int> v;
        for(int j=0;j<s.size();j++) {
            if(i & 1<<j) {
                v.push_back(s[j]);
            }
        }
        ans.push_back(v);
    }
    return ans;
}