Examples

//Given a set of distinct integers, nums, return all possible subsets (the power set).

//[1,2,3] => {[1],[2],[3], ...}

#include <iostream>

#include <vector>

using namespace std;

void backtrack(vector<vector<int>> & list, vector<int> & temp, vector<int> input, int start )

{

    list.push_back(temp);

    for(int i=start; i<input.size();i++){

        temp.push_back(input[i]);

        backtrack(list,temp,input, i+1);

        temp.pop_back();

    }

}

vector<vector<int>> combinations(vector <int> input)

{

    vector<vector<int>> results;

    vector<int> temp;

    backtrack(results,temp,input,0);

    for(int i=0; i<results.size();i++){

        for(int j=0; j< results.at(i).size();j++)

            cout<<results[i][j]<<",";

        cout<<endl;

    }

    return results;

}

int main()

{

    vector <int> input = {1,2,3};

    vector<vector<int>> results;

    results = combinations(input);

    return 0;

}

1.     1

2.     11

3.     21

4.     1211

5.     111221

#include <bits/stdc++.h>

using namespace std;

class Solution {

public:

    string countAndSay(int n) {

        string ss;

        //base

        if(n==1) {ss += "1"; return ss;}

        //read s at n-1

        string s = countAndSay(n-1);

        cout<<s<<endl;

        //create s at n

        //two indicators

        int start=s.length()-1, end=s.length()-1;

        //scan string from right to left

        while(end >= 0)

        {

            // find the duplicate char, begin from i, and start : return postion

            int num=0;

            string a = findDuplicateCharByPos(s,end,start, num);

            string b = to_string(num);

            ss= b+a+ss;

            end = start-1;

        }

        return ss;

    }

    string findDuplicateCharByPos(string s, int end, int & start, int & num)

    {

        string a = "";

        a.resize(1);

        a[0] = s[end];

        int count = 0;

        for (int i=end; i>=0;i--)

        {

            if(a[0]==s[i]) count++;

            else{break;}

        }

        start = end - count + 1;

        num = count;

        return a;

    }

};

int main()

{

    Solution A;

    cout<< A.countAndSay(4)<<endl;

    return 0;

}

#include <bits/stdc++.h>

using namespace std;

void printArray(int arr[], int n)

{

    cout<<"array of " << n << " elements:"<<endl;

    for (int i=0; i<n; i++)

        cout<< arr[i]<<",";

    cout<<endl;

}

void quicksort(int arr[], int start, int last)

{

    int pivot = last;

    //base case

    if (start >= last)

        return;

    //class the array into two arrays according to pivot

    for (int i=last;i>=start;i--)

    {

        if(arr[i] > arr[pivot]){

            swap(arr[i], arr[pivot]);

            pivot = i;

        }

    }

    cout<<"pivot = "<<pivot<<endl;

    // recursive the classified two arrays

    quicksort(arr, start, pivot-1);

    quicksort(arr, pivot+1, last);

    return;

}

// main function

int main()

{

    //set the init array

    int arr[] = {1,3,2,-1,32,21,16,45};

    int n = sizeof(arr)/sizeof(arr[0]);

    quicksort(arr,0,n-1);

    printArray(arr,n);

    return  0;

}

#include <iostream>

#include <vector>

#include <cmath>

#include <queue>

using namespace std;

// create priorityQueue class

class priorityQueue{

    // constructor

public:

    priorityQueue(vector<int>& data)

    {

        size = data.size();

        A = new int[size];

        for(int i=0;i<size;i++)

            A[i] = data[i];

        //create heap from an array

        int start = floor((size-2)/2);

        while(start>=0)

            heapify(start--);

    }

    int leftChild(int i) {return i*2+1; }

    int rightChild(int i) {return i*2+2; }

    void heapify(int i)

    {

        int left = leftChild(i);

        int right = rightChild(i);

        //cout<<"i="<<i<<";left = "<<left<<"; right="<<right<<endl;

        int smallest = i;

        // compare the values of children and the one of parent

        // in order to find the smallest one

        if(A[left] < A[smallest] && left < size) smallest = left;

        if(A[right] < A[smallest] && right < size) smallest = right;

        //cout<<"smallest="<<smallest<<endl;

        if(smallest != i){

//            int temp = A[i];

//            A[i] = A[smallest];

//            A[smallest] = temp;

            swap(A[i],A[smallest]);

            heapify(smallest);

        }

    }

    // deconstructor

    ~priorityQueue()

    {

        delete [] A;

    }

    bool empty()

    {

     //   cout<<"size="<<size<<endl;

        return size == 0;

    }

    int pop()

    {

        // remove the root of the heap

        if (size <=0) return -1;

        int top = A[0];

        // move the last to the top, redo heapify

        A[0] = A[size-1];

        size = size -1;

        heapify(0);

        return top;

    }

    // variable in class

    int * A;

    int size;

};

//heapsort

void heapSort(vector <int> &data)

{

    // contruct a priorityqueue

    priorityQueue pq(data);

    //put pq value back to vector data

    int i=0;

    while(!pq.empty()){

        data[i] = pq.pop();

        i++;

    }

}

// Print the elements in the vector

void printArray(vector <int> &data)

{

    int n = (int)data.size();

    cout << n <<endl;

    for(int i=0;i<n;i++)

        cout<<data[i]<<",";

    cout<<endl;

}

// main function for the heapsort

int main()

{

    //example

    vector <int> data = {12,1,23,45,11,5,7, 87,9};

    //printarray

    printArray(data);

//    //heapsort function

//    heapSort(data);

//    //printarray

//    printArray(data);

    cout<<"Another "<<endl;

    priority_queue<int, vector<int>,greater<int>> pq1(data.begin(),data.end());

    //put pq value back to vector data

    int i=0;

    while(!pq1.empty()){

        data[i++] = pq1.top();

        pq1.pop();

    }

    //printarray

    printArray(data);

}