# Recursion II

###### tags: `LeetCode筆記`

1. Divide and Conquer
2. Master theorem
3. Backtracking

## :memo: 一、Divide and Conquer

A divide-and-conquer algorithm works by recursively breaking the problem down into two or more subproblems of the same or related type, until these subproblems become **simple enough to be solved directly**. Then one combines the results of subproblems to form the final solution.

There are in general **three steps** that one can follow in order to solve the problem in a divide-and-conquer manner.



### Template Python

def divide_and_conquer( S ):
    # (1). Divide the problem into a set of subproblems.
    [S1, S2, ... Sn] = divide(S)

    # (2). Solve the subproblem recursively,
    #   obtain the results of subproblems as [R1, R2, ... Rn].
    rets = [divide_and_conquer(Si) for Si in [S1, S2, ... Sn]]
    [R1, R2, ... Rn] = rets

    # (3). combine the results from the subproblems.
    #   and return the combined result.
    return combine([R1, R2, ... Rn])

## :memo: Merge Sort

#### Top-down Approach


### 作法 C

void merge(int* nums, int left, int mid, int right){
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    
    int L[n1], R[n2];
    
    for (i = 0; i < n1; i++)
    {
        L[i] = nums[left + i];
    }
    
    for (j = 0; j < n2; j++)
    {
        R[j] = nums[mid + 1 + j];
    }
    
    i = 0;
    j = 0;
    k = left;
    
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            nums[k] = L[i];
            i++;
        }
        else
        {
            nums[k] = R[j];
            j++;
        }
        k++;
    }
    
    while (i < n1)
    {
        nums[k] = L[i];
        i++;
        k++;
    }
    
    while (j < n2)
    {
        nums[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int* nums, int left, int right) {
    if (left < right)
    {
        int mid = left + (right - left) / 2;
        
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        
        merge(nums, left, mid, right);
    }
}

int* sortArray(int* nums, int numsSize, int* returnSize){
    *returnSize = numsSize;
    
    mergeSort(nums, 0, numsSize - 1);
    
    return nums;
}

### 最快code C++
利用Hash Map概念去完成

int a[50001]={0};
int b[50001]={0};
class Solution {
public:
    vector<int> sortArray(vector<int>& v) {
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        for (auto x : v) {
            if (x >= 0) {
                a[x]++;
            }                
            else {
                b[-x]++;
            }                
        }
        
        v.clear();
        for(int i = 50000; i >= 1; i--) {
            if (b[i]) {
                while (b[i]) {
                    v.push_back(-i);
                    b[i]--;
                }
            }
        }
        for (int i = 0; i <= 50000; i++) {
            if (a[i]) {
                while (a[i]) {
                    v.push_back(i);
                    a[i]--;
                }
            }
        }
        
        return v;
    }
};

#### Bottom-up Approach


## :memo: Quick Sort

### 作法 Java

public class Solution {

    public void quickSort(int [] lst) {
    /* Sorts an array in the ascending order in O(n log n) time */
        int n = lst.length;
        qSort(lst, 0, n - 1);
    }

    private void qSort(int [] lst, int lo, int hi) {
        if (lo < hi) {
            int p = partition(lst, lo, hi);
            qSort(lst, lo, p - 1);
            qSort(lst, p + 1, hi);
        }
    }

    private int partition(int [] lst, int lo, int hi) {
    /*
    Picks the last element hi as a pivot
    and returns the index of pivot value in the sorted array 
    */
        int pivot = lst[hi];
        int i = lo;
        for (int j = lo; j < hi; ++j) {
            if (lst[j] < pivot) {
                int tmp = lst[i];
                lst[i] = lst[j];
                lst[j] = tmp;
                i++;
            }
        }
        int tmp = lst[i];
        lst[i] = lst[hi];
        lst[hi] = tmp;
        return i;
    }
}

## :memo: 二、Master Theorem

https://leetcode.com/explore/learn/card/recursion-ii/470/divide-and-conquer/2871/

## :memo: Validate Binary Search Tree (Medium)
Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A **valid BST** is defined as follows:

* The left subtree of a node contains only nodes with keys **less than** the node's key.
* The right subtree of a node contains only nodes with keys **greater than** the node's key.
* Both the left and right subtrees must also be binary search trees.

### 作法
我的作法是用LDR去treaverse存成一個陣列，然後用複製一份陣列後用MergeSort排序比對兩個陣列，這樣很耗時也沒必要。

### 作法 C++

class Solution {
public:
    bool validate(TreeNode* root, TreeNode* low, TreeNode* high) {
        // Empty trees are valid BSTs.
        if (root == nullptr) {
            return true;
        }

        // The current node's value must be between low and high.
        if ((low != nullptr and root->val <= low->val) or
            (high != nullptr and root->val >= high->val)) {
            return false;
        }

        // The left and right subtree must also be valid.
        return validate(root->right, root, high) and
               validate(root->left, low, root);
    }

    bool isValidBST(TreeNode* root) {
        return validate(root, nullptr, nullptr);
    }
};

### 最快code 0ms C++
加入自定義最大值INT64_MAX和最小值INT64_MIN去加快效率

class Solution {
public:
    bool isValidBST(TreeNode *root, long minVal, long maxVal) {
        if (root == NULL) {
            return true;
        }            

        if (root->val >= maxVal || root->val <= minVal) {
            return false;
        }            

        bool left = isValidBST(root->left, minVal, root->val);
        bool right = isValidBST(root->right, root->val, maxVal);

        return left && right;
    }
    
    bool isValidBST(TreeNode* root) {
        return isValidBST(root, INT64_MIN, INT64_MAX);
    }
};

## :memo: Search a 2D Matrix II (Medium)
Write an efficient algorithm that searches for a value target in an m x n integer matrix.

This matrix has the following properties:

* Integers in each row are sorted in ascending from left to right.
* Integers in each column are sorted in ascending from top to bottom.



### 作法

這題的陣列從左到右從上到下是由小到大排序好的順序，將問題切成左下一塊右上一塊的子問題，如果一開始就小於子問題的左上角或大於子問題的右下角就回傳false，都沒有就切一半mid = left + (right - left) / 2，從mid那一行往下找target，都沒找到就繼續去切成兩塊子問題

bool searchRec(int** matrix, int left, int up, int right, int down, int target) {
    if (left > right || up > down)
    {
        return false;
    }
    else if (target < matrix[up][left] || target > matrix[down][right])
    {
        return false;
    }
    
    int mid = left + (right - left) / 2;
    
    int row = up;
    while (row <= down && matrix[row][mid] <= target)
    {
        if (matrix[row][mid] == target)
        {
            return true;
        }
        row++;
    }

    return searchRec(matrix, left, row, mid - 1, down, target) || searchRec(matrix, mid + 1, up, right, row - 1, target);
}

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    if (matrix == NULL || matrixSize == 0)
    {
        return false;
    }
    
    return searchRec(matrix, 0, 0, (*matrixColSize) - 1, matrixSize - 1, target);
}

### 作法 Binary Search Python

class Solution:
    def binary_search(self, matrix, target, start, vertical):
        lo = start
        hi = len(matrix[0]) - 1 if vertical else len(matrix) - 1

        while hi >= lo:
            mid = (lo + hi) // 2
            if vertical: # searching a column
                if matrix[start][mid] < target:
                    lo = mid + 1
                elif matrix[start][mid] > target:
                    hi = mid - 1
                else:
                    return True
            else: # searching a row
                if matrix[mid][start] < target:
                    lo = mid + 1
                elif matrix[mid][start] > target:
                    hi = mid - 1
                else:
                    return True
        
        return False

    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        # an empty matrix obviously does not contain `target`
        if not matrix:
            return False

        # iterate over matrix diagonals starting in bottom left.
        for i in range(min(len(matrix), len(matrix[0]))):
            vertical_found = self.binary_search(matrix, target, i, True)
            horizontal_found = self.binary_search(matrix, target, i, False)
            if vertical_found or horizontal_found:
                return True
        
        return False

### 作法 Search Space Reduction 最快code C++
**時間: O(n+m)**
**空間: O(1)**

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        ios::sync_with_stdio(0);
        int m = matrix.size();
        int n = matrix[0].size();

        int i = 0;
        int j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                matrix.clear();
                return true;
            }
            else if (matrix[i][j] > target) {
                j--;
            }                
            else {
                i++;
            }                
        }
        matrix.clear();
        
        return false;
    }
};

## :memo: 三、Backtracking
Conceptually, one can imagine the procedure of backtracking as the **tree traversal**. Starting from the root node, one sets out to search for solutions that are located at the leaf nodes. Each intermediate node represents **a partial candidate solution** that could potentially lead us to a final valid solution. At each node, we would fan out to move one step further to the final solution, i.e. we iterate the child nodes of the current node. Once we can determine if a certain node **cannot** possibly lead to a valid solution, we **abandon the current node** and **backtrack to its parent node** to explore other possibilities. It is due to this backtracking behaviour, the backtracking algorithms are often much faster than the brute-force search algorithm, since it **eliminates many unnecessary exploration**.

### Template Python

def backtrack(candidate):
    if find_solution(candidate):
        output(candidate)
        return
    
    # iterate all possible candidates.
    for next_candidate in list_of_candidates:
        if is_valid(next_candidate):
            # try this partial candidate solution
            place(next_candidate)
            # given the candidate, explore further.
            backtrack(next_candidate)
            # backtrack
            remove(next_candidate)

### Example 1



### Example 2


In order to count the number of possible solutions to place the N queens, we can break it down into the following steps:

1. Overall, we **iterate over each row** in the board, i.e. once we **reach the last row** of the board, we should **have explored all the possible solutions**.
2. **At each iteration** (we are located at certain row), we **then further iterate over each column** of the board, along the current row. At this second iteration, we then can **explore** the possibility of placing a queen on a particular cell.
3. Before, we place a queen on the cell with index of (row, col), we need to check if this cell is under the attacking zone of the queens that have been placed on the board before. Let us assume there is a function called **is_not_under_attack(row, col)** that can do the check.
4. Once the check passes, we then can proceed to place a queen. Along with the placement, one should also mark out the attacking zone of this newly-placed queen. Let us assume there is another function called **place_queen(row, col)** that can help us to do so.
5. As an important behaviour of backtracking, we should be able to abandon our previous decision at the moment we decide to move on to the next candidate. Let us assume there is a function called **remove_queen(row, col)** that can help us to revert the decision along with the changes in step (4).

Now, with the above steps and functions, we can organize them in the form of recursion in order to implement the algorithm. In the following, we present the **pseudocode** of the backtracking algorithm.

### Pseudocode Python3

def backtrack_nqueen(row = 0, count = 0):
    for col in range(n):
        # iterate through columns at the curent row.
        if is_not_under_attack(row, col):
            # explore this partial candidate solution, and mark the attacking zone
            place_queen(row, col)
            if row + 1 == n:
                # we reach the bottom, i.e. we find a solution!
                count += 1
            else:
                # we move on to the next row
                count = backtrack_nqueen(row + 1, count)
            # backtrack, i.e. remove the queen and remove the attacking zone.
            remove_queen(row, col)
    return count

## :memo: N-Queens II (Hard)


### 作法 C
使用backtrack algorithm去解
在跑col的for迴圈裡面做以下事情:
1. 先判斷是否有效的放置皇后is_not_under_attack(matrix,row,col,matrixSize)，
2. 如果有效就放置皇后place_queen(matrix,row,col)，
3. 接著判斷是否到最後一列，是就解法數加一count++，
4. 沒有到最後一列就row+1後去backtrack遞迴count = backtrack_nqueen(matrix,row+1,count,matrixSize)，
5. 遞迴回來後就移除皇后remove_queen(matrix,row,col)

bool is_not_under_attack(int** matrix, int row, int col, int matrixSize) {
    for (int i = row; i >= 0; i--)
    {
        if (matrix[i][col] == 1)
        {
            return false;
        }
    }
    for (int i = row; i < matrixSize; i++)
    {
        if (matrix[i][col] == 1)
        {
            return false;
        }
    }
    for (int i = col; i >= 0; i--)
    {
        if (matrix[row][i] == 1)
        {
            return false;
        }
    }
    for (int i = col; i < matrixSize; i++)
    {
        if (matrix[row][i] == 1)
        {
            return false;
        }
    }
    for (int i = row, j = col; i < matrixSize && j < matrixSize; i++, j++)
    {
        if (matrix[i][j] == 1)
        {
            return false;
        }
    }
    for (int i = row, j = col; i >= 0 && j < matrixSize; i--, j++)
    {
        if (matrix[i][j] == 1)
        {
            return false;
        }
    }
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)
    {
        if (matrix[i][j] == 1)
        {
            return false;
        }
    }
    for (int i = row, j = col; i < matrixSize && j >= 0; i++, j--)
    {
        if (matrix[i][j] == 1)
        {
            return false;
        }
    }
    
    return true;
}

void place_queen(int** matrix, int row, int col) {
    matrix[row][col] = 1;
}

void remove_queen(int** matrix, int row, int col) {
    matrix[row][col] = 0;
}

int backtrack_nqueen(int** matrix, int row, int count, int matrixSize) {
    for (int col = 0; col < matrixSize; col++)
    {
        if (is_not_under_attack(matrix, row, col, matrixSize))
        {
            place_queen(matrix, row, col);            
            if (row + 1 == matrixSize)
            {
                count++;
            }
            else
            {
                count = backtrack_nqueen(matrix, row + 1, count, matrixSize);
            }
            remove_queen(matrix, row, col);
        }
    }

    return count;
}

int totalNQueens(int n) {
    int** matrix = (int**) malloc(sizeof(int*) * n);
    for (int i = 0; i < n; i++)
    {
        matrix[i] = (int*) malloc(sizeof(int) * n);
        for (int j = 0; j < n; j++)
        {
            matrix[i][j] = 0;
        }
    }
    int count = 0;
    
    return backtrack_nqueen(matrix, 0, count, n);
}

### 作法 C++
record what like:

class Solution {
public:
    bool isValid(vector<string>& board, int row, int col) {
        // up
        for (int i = row - 1; i >= 0; i--) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        // left up
        for (int i = row - 1, j = col - 1; i >= 0 and j >= 0; i-- ,j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        // right up
        for (int i = row - 1, j = col + 1; i >= 0 and col < board[0].size(); i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }
    void backtrack(vector<vector<string>>& res, vector<string>& board, int n, int row) {
        for (int col = 0; col < n; col++) {
            if (isValid(board, row, col)) {
                board[row][col] = 'Q';
                if (row == n - 1) {
                    res.push_back(board);
                } else {
                    backtrack(res, board, n, row + 1);
                }                
                board[row][col] = '.';
            }                  
        }
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> board(n, string(n, '.'));

        backtrack(res, board, n, 0);

        return res;
    }
};

## :memo: Robot Room Cleaner (Hard)




### 作法 C++
到新的格子就去標記已拜訪和清潔，接著用標準搜尋2D-array做法去跑4個方向(上下左右)的for迴圈，在跑4個方向的for迴圈裡面做以下事情:
1. 要加上是否**拜訪**(visited)和是否有效移動一起判斷，
2. 符合就backtrack遞迴到新方向的格子
3. 遞迴回來就goBack(robot)
4. 再for迴圈最後一行要向右轉turnRight()

/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * class Robot {
 *   public:
 *     // Returns true if the cell in front is open and robot moves into the cell.
 *     // Returns false if the cell in front is blocked and robot stays in the current cell.
 *     bool move();
 *
 *     // Robot will stay in the same cell after calling turnLeft/turnRight.
 *     // Each turn will be 90 degrees.
 *     void turnLeft();
 *     void turnRight();
 *
 *     // Clean the current cell.
 *     void clean();
 * };
 */

class Solution {
private:
    set<pair<int, int>> visited;
    vector<vector<int>> directions{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
  
    void goBack(Robot& robot) {
        robot.turnRight();
        robot.turnRight();
        robot.move();
        robot.turnRight();
        robot.turnRight();  
    }
    
    void backtrack(Robot& robot, int row, int col, int dir) {
        visited.insert({row, col});
        robot.clean();
        
        for (int i = 0; i < 4; i++) {
            int newD = (dir + i) % 4;
            int newRow = row + directions[newD][0];
            int newCol = col + directions[newD][1];
            
            if (!visited.count({newRow, newCol}) && robot.move()) {
                backtrack(robot, newRow, newCol, newD);
                goBack(robot);
            }
            
            robot.turnRight();
        }        
    }

public:
    void cleanRoom(Robot& robot) {
        backtrack(robot, 0, 0, 0);
    }
};

### 最快code 3ms C++

class Solution {
public:
    void cleanRoom(Robot& robot) {
        backtrack(robot, {0, 0}, 0);
    }
    
private:
    typedef struct {
        int row;
        int col;
    } Ceil;
    
    struct CeilHash {
        size_t operator()(const Ceil& ceil) const {
            return ceil.row * 1000 + ceil.col;
        }
    };
    
    struct CeilEqualTo {
        bool operator()(const Ceil& ceil1, const Ceil& ceil2) const {
            return ceil1.row == ceil2.row && ceil1.col == ceil2.col;
        }
    };
    
    unordered_set<Ceil, CeilHash, CeilEqualTo> _visited;
    
    // directions: 0 - up, 1 - right, 2 - down, 3 - left
    const int DIRECTIONS[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
    //
    // backtrack
    //
    void backtrack(Robot& robot, const Ceil& ceil, int direction) {
        robot.clean();
        _visited.insert(ceil);
        
        for (int n = 0; n < 4; n++) {
            int new_direction = (direction + n) % 4;
            const auto& dir = DIRECTIONS[new_direction];
            Ceil new_ceil = {ceil.row + dir[0], ceil.col + dir[1]};
            if (_visited.find(new_ceil) == _visited.end()) {
                if (robot.move()) {
                    backtrack(robot, new_ceil, new_direction);
                    
                    // move back
                    robot.turnRight();
                    robot.turnRight();
                    robot.move();
                    robot.turnRight();
                    robot.turnRight();
                }
            }
            
            robot.turnRight();
        }
    }
};

## :memo: Sudoku Solver (Hard)



### 作法 C
這題解數獨有三個地方想不到:
1.backtrack function回傳布林值
2.用nested for (col in row) 去塞code
3.backtrack遞迴放在哪一個位置

bool is_valid(char** board, char val, int row, int col) {
    int row_start = (row / 3) * 3;
    int row_end = (row / 3 + 1) * 3;
    int col_start = (col / 3) * 3;
    int col_end = (col / 3 + 1) * 3;
    
    for (int i = 0; i < 9; i++)
    {
        if (board[row][i] == val)
        {
            return false;
        }
    }
    for (int i = 0; i < 9; i++)
    {
        if (board[i][col] == val)
        {
            return false;
        }
    }
    for (int i = row_start; i < row_end; i++)
    {
        for (int j = col_start; j < col_end; j++)
        {
            if (board[i][j] == val)
            {
                return false;
            }
        }
    }
    
    return true;
}

void place_val(char** board, char val, int row, int col) {
    board[row][col] = val;
}

void remove_val(char** board, int row, int col) {
    board[row][col] = '.';
}

//用成布林想不到
bool backtrack(char** board, int size) {
    for (int row = 0; row < size; row++)
    {
        for (int col = 0; col < size; col++)
        {
            if (board[row][col] == '.')
            {
                // try every number from 1 to 9 in this cell
                for (char val = '1'; val <= '9'; val++)
                {
                    if (is_valid(board, val, row, col))
                    {
                        place_val(board, val, row, col);
                        // recursively try other cells
                        //======這段想不到======
                        if (backtrack(board, size))
                        {
                            return true;
                        }                            
                        else
                        {
                            remove_val(board, row, col);   // reset the cell to try other numbers
                        }
                        //======================
                    }
                }
                return false;
            }
        }
    }
    return true;
}

void solveSudoku(char** board, int boardSize, int* boardColSize) {
    // fill the empty cells using backtrack strategy
    backtrack(board, boardSize);    
}

### 作法 Bit manipulation 最快code C++

class Solution {
public:
    vector<pair<int, int>> emptyCells;
    int rows[9] = {}, cols[9] = {}, boxes[9] = {};
    void solveSudoku(vector<vector<char>>& board) {
        for (int r = 0; r < 9; r++) {
            for (int c = 0; c < 9; c++) {
                if (board[r][c] == '.') {
                    emptyCells.emplace_back(r, c);
                } else {
                    int val = board[r][c] - '0';
                    int boxPos = (r / 3) * 3 + (c / 3);
                    rows[r] |= 1 << val;
                    cols[c] |= 1 << val;
                    boxes[boxPos] |= 1 << val;
                }
            }
        }
        backtracking(board, 0);
    }
    bool backtracking(vector<vector<char>>& board, int i) {
        if (i == emptyCells.size()) {
            return true; // Check if we filled all empty cells?
        }
        
        int r = emptyCells[i].first, c = emptyCells[i].second, boxPos = (r / 3) * 3 + c / 3;
        for (int val = 1; val <= 9; ++val) {
            if (getBit(rows[r], val) || getBit(cols[c], val) || getBit(boxes[boxPos], val)) {
                continue; // skip if that value is existed!
            }
            board[r][c] = ('0' + val);
            int oldRow = rows[r], oldCol = cols[c], oldBox = boxes[boxPos]; // backup old values
            rows[r] |= 1 << val;
            cols[c] |= 1 << val;
            boxes[boxPos] |= 1 << val;
            if (backtracking(board, i + 1)) {
                return true;
            }
            rows[r] = oldRow; // backtrack
            cols[c] = oldCol; // backtrack
            boxes[boxPos] = oldBox; // backtrack
        }
        return false;
    }
    int getBit(int x, int k) {
        return (x >> k) & 1;
    }
};

## :memo: Combinations (Medium)

### 作法 C
一樣用backtrack algorithm去解，畫樹狀圖可以方便理解

bool is_valid(int* temp, int index, int val) {
    for (int i = 0; i < index; i++)
    {
        if (temp[i] >= val)
        {
            return false;
        }
    }
    return true;
}

void place_val(int* temp, int index, int val) {
    temp[index] = val;
}

void remove_val(int* temp, int index) {
    temp[index] = 0;
}

void backtrack(int** ret, int* num, int index, int* temp, int n, int k) {
    for (int val = 1; val <= n; val++)
    {
        if (is_valid(temp, index, val))
        {
            place_val(temp, index, val);
            // printf("temp[index] = %d index = %d\n", temp[index], index);
            // printf("show temp:\n");
            // for (int i = 0; i < 2; i++)
            // {
            //     printf("%d \n", temp[i]);
            // }
            // printf("=======\n");
            if (index == k - 1)
            {
                for (int i = 0; i < k; i++)
                {
                    ret[*num][i] = temp[i];
                }
                // printf("index = %d\n", index);
                // printf("ret[%d][0, 1]=[%d, %d]\n",*num, ret[*num][0], ret[*num][1]);
                (*num)++;            
            }
            else
            {
                // printf("go to backtrack *num = %d index = %d\n", *num, index);
                backtrack(ret, num, index + 1, temp, n, k);    
            }            
        }
        remove_val(temp, index);
    }
    //printf("%d over %d %d\n", *num, ret[*num][0], ret[*num][1]);
}
int** combine(int n, int k, int* returnSize, int** returnColumnSizes) {
    long long numerator = 1;
    long long denominator  = 1;
    int total = 0;
    
    for (int i = n; i >= n - (k - 1); i--)
    {
        numerator *= i;
    }
    for (int i = 1; i <= k; i++)
    {
        denominator *= i;
    }
    total = numerator / denominator;
    // printf("%d %d %d\n",total,n,k);
    
    *returnSize = total;
    int** ret = (int**) malloc(sizeof(int*) * total);
    *returnColumnSizes = (int*) malloc(sizeof(int) * total);
    for (int i = 0; i < total; i++)
    {
        ret[i] = (int*) malloc(sizeof(int) * k);
        (*returnColumnSizes)[i] = k;
    }
    
    if (k == 1)
    {
        int c = 1;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < k; j++)
            {
                ret[i][j] = c;
                c++;
            }
        }
        
        return ret;
    }
        
    int num = 0;
    int index = 0;
    int* temp = (int*) malloc(sizeof(int) * k);
    for (int i = 0; i < k; i++)
    {
        temp[i] = 0;
    }
    backtrack(ret, &num, index, temp, n, k);   
   
    return ret;
}

### 作法 C++

class Solution {
public:
    void backtrack(int n, int k, int index, vector<int>& temp, vector<vector<int>>& res) {
        for (int i = index; i <= n; i++) {
            temp.push_back(i);
            if (temp.size() == k) {
                res.push_back(temp);
            }
            else {
                backtrack(n, k, i + 1, temp, res);
            }
            temp.pop_back();            
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> temp;

        backtrack(n, k, 1, temp, res);

        return res;
    }
};

## :memo: Permutations (Medium)

### 作法 C
這題基於Combinations去改，改is_valid()，>=變==

bool is_valid(int* temp, int index, int val) {
    for (int i = 0; i < index; i++)
    {
        if (temp[i] == val)
        {
            return false;
        }
    }
    return true;
}

void place_val(int* temp, int index, int val) {
    temp[index] = val;
}

void remove_val(int* temp, int index) {
    temp[index] = 0;
}

void backtrack(int** ret, int* num, int* nums, int index, int* temp, int n, int k) {
    for (int val = 0; val < n; val++)
    {
        if (is_valid(temp, index, nums[val]))
        {
            place_val(temp, index, nums[val]);
            // printf("temp[index]=%d index=%d\n",temp[index],index);
            // printf("show temp:\n");
            // for(int i=0;i<n;i++)
            // {
            //     printf("%d \n",temp[i]);
            // }
            // printf("---------------\n");
            if (index == k - 1)
            {
                for (int i = 0; i < k; i++)
                {
                    ret[*num][i] = temp[i];
                }
                // printf("index = %d\n",index);
                // for(int i=0;i<k;i++)
                // {
                //     printf("ret[%d][%d] = %d\n",*num,i,ret[*num][i]);
                // }
                // printf("========================\n\n");
                (*num)++;            
            }
            else
            {
                // printf("go to backtrack *num=%d index=%d\n",*num,index);
                backtrack(ret, num, nums, index + 1, temp, n, k);    
            }            
        }
        remove_val(temp, index);
    }
}

int** permute(int* nums, int numsSize, int* returnSize, int** returnColumnSizes) {
    long long numbers = 1;
    
    for (int i = 1; i <= numsSize; i++)
    {
        numbers *= i;
    }

    // printf("numbers =  %d\n\n",numbers);
    
    *returnSize = numbers;
    int** ret = (int**) malloc(sizeof(int*) * numbers);
    *returnColumnSizes = (int*) malloc(sizeof(int) * numbers);
    for (int i = 0; i < numbers; i++)
    {
        ret[i] = (int*) malloc(sizeof(int) * numsSize);
        (*returnColumnSizes)[i] = numsSize;
    }
    
    if (numsSize == 1)
    {
        for (int i = 0; i < numsSize; i++)
        {
            for (int j = 0; j < numsSize; j++)
            {
                ret[i][j] = nums[0];
            }
        }
        
        return ret;
    }
        
    int number = 0;
    int index = 0;
    int* temp = (int*) malloc(sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; i++)
    {
        temp[i] = 0;
    }
    backtrack(ret, &number, nums, index, temp, numsSize, numsSize);   
   
    return ret;
}

### 作法 用swap C++

class Solution {
public:
    void permuteRecursive(vector<int> &nums, int begin, vector<vector<int>> &result) {
        if (begin >= nums.size()) {
            result.push_back(nums);
            return;
        }
        
        for (int i = begin; i < nums.size(); i++) {
            swap(nums[begin], nums[i]);
            permuteRecursive(nums, begin + 1, result);
            swap(nums[begin], nums[i]);
        }
    }
    
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> result;
        
        permuteRecursive(nums, 0, result);
        
        return result;
    }
};

## :memo: 四、Recursion to Iteration
Reasons:
1. Risk of Stackoverflow
2. Efficiency
3. Complexity

To **convert a recursion approach to an iteration one**, we could perform the following two steps:

1. We use **a stack or queue data structure** within the function, to replace the role of the system call stack. At each occurrence of recursion, we simply push the parameters as a new element into the data structure that we created, instead of invoking a recursion.
2. In addition, we create **a loop over the data structure** that we created before. The chain invocation of recursion would then be replaced with the iteration within the loop.

## :memo: Same Tree (Easy)


### 作法 recursion

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (p == NULL && q == NULL) {
            return  true;
        }
        if (p == NULL && q != NULL) {
            return false;
        }
        if (p != NULL && q == NULL) {
            return false;
        }

        bool left = isSameTree(p->left, q->left);
        bool right = isSameTree(p->right, q->right);

        bool value = p->val == q->val;

        if (value && left && right) {
            return true;
        }
        else {
            return false;
        }
    }
};

### 作法 iteration

class Solution {
public:
    bool check(TreeNode* p, TreeNode* q) {
        if (p == nullptr && q == nullptr) {
            return true;
        }
        if (p == nullptr || q == nullptr) {
            return false;
        }
        if (p->val != q->val) {
            return false;
        }
        
        return true;
    }
    bool isSameTree(TreeNode* p, TreeNode* q) {
        queue<TreeNode*> qp;
        queue<TreeNode*> qq;
        
        qp.push(p);
        qq.push(q);
        
        while(qp.size() > 0 && qq.size() > 0) {
            TreeNode* Tp = qp.front();
            TreeNode* Tq = qq.front();
            
            qp.pop();
            qq.pop();
            if (check(Tp, Tq)) {
                if (Tp != nullptr && Tq != nullptr) {
                    if (check(Tp->left, Tq->left)) {
                        qp.push(Tp->left);
                        qq.push(Tq->left);
                    }
                    else {
                        return false;
                    }
                    if (check(Tp->right, Tq->right)) {
                        qp.push(Tp->right);
                        qq.push(Tq->right);
                    }
                    else {
                        return false;
                    }
                }                
            }
            else {
                return false;
            }
        }
        
        return true;
    }
};

## :memo: Binary Tree Inorder Traversal (Easy)


### 作法 iteration with stack

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> s;
        vector<int> ans;
        
        TreeNode* curr = root;
        while (curr != nullptr || !s.empty()) {
            while (curr != nullptr) {
                s.push(curr);
                curr = curr->left;
            }
            curr = s.top();
            s.pop();
            ans.push_back(curr->val);
            curr = curr->right;
        }
        
        return ans;
    }
};

## :memo: Generate Parentheses (Medium)

### 作法 C
這一題主要要先用tmp去存暫時的答案，當寫滿括號後再複製到ret裡面，而function方面是如何寫is_valid()，條件是右括號數量不能大於左括號數量，左括號數量不能大於總長度

bool is_valid(char* tmp, int index, char c, int length) {
    char temp[1];
    int left_bracket = 0;
    int right_bracket = 0;
    
    temp[0] = tmp[index];
    tmp[index] = c;
    for (int i = 0; i <= index; i++)
    {
        if (tmp[i] == '(')
        {
            left_bracket++;
        }
        else if (tmp[i] == ')')
        {
            right_bracket++;
        }
        if (right_bracket > left_bracket)
        {
            tmp[index] = temp[0];
            return false;
        }
        if (left_bracket > length)
        {
            tmp[index] = temp[0];
            return false;
        }
    }
    tmp[index] = temp[0];
    return true;
}

void foo(char** ret, int* n, int index, char c, int size, char* tmp) {
    if (index == size)
    {
        tmp[index] = '\0';
        // printf("tmp = %s\n",tmp);
        char *new = malloc(sizeof(char) * (size + 1));
        memcpy(new, tmp, sizeof(char) * (size + 1));
        // printf("new = %s\n",new);
        ret[*n] = new;
        // printf("num %d =  %s\n",*n,ret[*n]);
        (*n)++;
        return;
    }
    else
    {
        if (is_valid(tmp, index, '(', size/2))
        {
            tmp[index] = '(';            
            foo(ret, n, index + 1, '(', size, tmp);    
        }
        if (is_valid(tmp, index, ')', size / 2))
        {
            tmp[index] = ')';
            foo(ret, n, index + 1, ')', size, tmp);    
        }        
    }
}

char ** generateParenthesis(int n, int* returnSize) {
    int pow = 1;
    for (int i = 0; i < 2 * n; i++)
    {
        pow *= 2;
    }
    // printf("%d\n",pow);
    char** ret = (char**) malloc(sizeof(char*) * pow);
    for (int i = 0; i < pow; i++)
    {
        ret[i] = (char*) malloc(sizeof(char) * (2 * n + 1));
    }
    
    int num = 0;
    int index = 0;
    int size = 2 * n;
    char tmp[20];
    foo(ret, &num, index, '(', size, tmp);
    
    // printf("num = %d\n",num);
    
    *returnSize = num;    
    return ret;
}

### 作法 iteration C++

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        queue<string> q;
        vector<string> ans;
        
        q.push("(");        
        while (!q.empty()) {
            string s = q.front();
            q.pop();
            
            string temp;
            temp = s + '(';
            if (count(s.begin(), s.end(), '(') < n) {
                q.push(temp);
            }
            temp = s + ')';
            if (count(s.begin(), s.end(), '(') > count(s.begin(), s.end(), ')')) {
                q.push(temp);
            }
            if (temp.size() == n * 2) {
                ans.push_back(temp);
            }
        }
        
        return ans;
    }
};

### 作法 recursion 0ms C++

class Solution {
public:
    void func(vector<string> &ans, string s, int open, int close, int n) {
        if (s.length() == n * 2) {
            ans.push_back(s);
            s = "";
            return ;
        }
        if (open == n) {
            for (int idx = 0; idx < n - close; idx++) {
                s += ')';
            }
            ans.push_back(s);
            return;
        }
        if (open == n and close == n) {            
            ans.push_back(s);
            return;
        }
        if (open < n) {
            func(ans, s + '(', open + 1, close, n);
        }
        if (close < open) {
            func(ans, s + ')', open, close + 1, n);
        }   
    }
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        func(ans, "", 0, 0, n);

        return ans;
    }
};

## :memo: Letter Combinations of a Phone Number (Medium)


### 作法
一樣是backtracking，這題的code有做整理，看起來有點clean code^^

char letters[8][4] = {
    {'a', 'b', 'c'},
    {'d', 'e', 'f'},
    {'g', 'h', 'i'},
    {'j', 'k', 'l'},
    {'m', 'n', 'o'},
    {'p', 'q', 'r', 's'},
    {'t', 'u',' v'},
    {'w', 'x', 'y', 'z'}
};

char number[8] = {'2', '3', '4', '5', '6', '7', '8', '9'};
int size[8] = {3, 3, 3, 3, 3, 4, 3, 4};

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

void is_end(char* digits, int index, char* temp, char** ret, int* num) {
    if (digits[index + 1] == '\0')
    {
        temp[index + 1] = '\0';
        char* newString = (char*) malloc(sizeof(char) * (strlen(digits) + 1));
        memcpy(newString, temp, sizeof(char) * (strlen(digits) + 1));
        ret[*num] = newString;
        (*num)++;
    }
}


void place_letter(char* temp, int index, char letter) {
    temp[index] = letter;
}

void backtrack(char** ret, int* num, char* digits, char* temp, int index) {
    for (int i = 0; i < 8; i++)
    {
        if (digits[index] == number[i])
        {
            for (int j = 0; j < size[i]; j++)
            {
                place_letter(temp, index, letters[i][j]);
                is_end(digits, index, temp, ret, num);
                backtrack(ret, num, digits, temp, index + 1);
            }            
        }
    }
}

char ** letterCombinations(char * digits, int* returnSize) {
    char** ret = (char**) malloc(sizeof(char*) * 256);
    for (int i = 0; i < 256; i++)
    {
        ret[i] = (char*) malloc(sizeof(char) * (strlen(digits) + 1));
    }
    
    int num = 0;
    int index = 0;
    char temp[20];
    
    backtrack(ret, &num, digits, temp, index);
    
    *returnSize = num;    
    return ret;
}

## :memo: Convert Binary Search Tree to Sorted Doubly Linked List (Medium)



### 作法 C

void convert(struct Node** prev, struct Node* current, struct Node** newHead) {
    if (current == NULL)
    {
        return;
    }
    
    convert(prev, current->left, newHead);
    
    if (*prev == NULL)
    {
        *newHead = current;
    }
    else
    {
        (*prev)->right = current;
        current->left = *prev;
    }

    *prev = current;
    
    convert(prev, current->right, newHead);
}


struct Node* treeToDoublyList(struct Node *root) {
    if (root == NULL)
    {
        return  NULL;
    }
    
    struct Node* prev = NULL;
    struct Node* current = root;
    struct Node* newHead = NULL; // the leftmost(smallest element)
    
    convert(&prev, current, &newHead);
    
    // link the last element to the original root
    newHead->left = prev;
    prev->right = newHead;
    
    return  newHead;
}

### 作法 C++

class Solution {
public:
    Node* first = nullptr;
    Node* last = nullptr;

    void helper(Node* node) {
        if (node) {
            helper(node->left);

            if (last) {
                last->right = node;
                node->left = last;
            }
            else {
                first = node;
            }

            last = node;

            helper(node->right);
        }
    }
    
    Node* treeToDoublyList(Node* root) {
        if (!root) {
            return nullptr;
        }
        
        helper(root);
        
        last->right = first;
        first->left = last;
        
        return first;
    }
};

## :memo: Largest Rectangle in Histogram (Hard)


**這題要用stack去解才不會TLE**
### 作法 C

#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))

typedef struct stackt {
    int *arr;
    int top;
    int stackSize;
}stackT;

bool isStackEmpty(stackT *stack) {
    return stack->top == -1;
}

bool isStackFull(stackT *stack) {
    return stack->top == stack->stackSize;
}

stackT *createStack(int stackSize) {
    stackT *stack = malloc(sizeof(stackT));
    if (!stack) {
        return NULL;
    } 
    stack->arr = malloc(sizeof(int) * stackSize);
    if (!stack->arr) {
        return NULL;
    } 
    stack->top = -1;
    stack->stackSize = stackSize;
    return stack;
}

int stackPush(stackT *stack, int inputIdx) {
    if (isStackFull(stack)) {
        return -1;
    } 
    stack->arr[++stack->top] = inputIdx;
    return 1;
}

int stackPop(stackT *stack) {
    if (isStackEmpty(stack)) {
        return -1;
    } 
    return stack->arr[stack->top--];
}

int stackPeek(stackT *stack) {
    if (isStackEmpty(stack)) {
        return -1;
    } 
    return stack->arr[stack->top];
}

void freeStack(stackT *stack) {
    free(stack->arr);
    free(stack);
}

int largestRectangleArea(int* heights, int heightsSize) {
    int rowSize = heightsSize;
    int maxArea = 0;
    
    stackT *stack = createStack(heightsSize);
    if(!stack)  return false;
    
    for (int i = 0; i < rowSize; i++)
    {
        while ((!isStackEmpty(stack)) && (heights[stackPeek(stack)] >= heights[i]))
        {
            int currentHeight = heights[stackPop(stack)];
            int currentWidth = i - stackPeek(stack) - 1;
            maxArea = MAX(maxArea, currentHeight * currentWidth);
        }
        stackPush(stack, i);
    }
    
    while (!isStackEmpty(stack))
    {
        int currentHeight = heights[stackPop(stack)];
        int currentWidth = rowSize - stackPeek(stack) -1 ;
        maxArea = MAX(maxArea, currentHeight * currentWidth);
    }
   return maxArea;    
}

### 作法 C++

class Solution {
public:   
    int largestRectangleArea(vector<int>& heights) {
        stack<int> stk;
        stk.push(-1);
        int max_area = 0;
        
        for (size_t i = 0; i < heights.size(); i++) {
            while (stk.top() != -1 and heights[stk.top()] >= heights[i]) {
                int current_height = heights[stk.top()];
                stk.pop();
                int current_width = i - stk.top() - 1;
                max_area = max(max_area, current_height * current_width);
            }
            stk.push(i);
        }
        
        while (stk.top() != -1) {
            int current_height = heights[stk.top()];
            stk.pop();
            int current_width = heights.size() - stk.top() - 1;
            max_area = max(max_area, current_height * current_width);
        }
        
        return max_area;
    }
};

### 最快code

int hgt[100001];
int pos[100001];
class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        heights.push_back(0);
        int ans = heights[0], n = heights.size(), m = 0;
        hgt[0] = eights[0];
        pos[0] = 0;
        for (int i = 1; i < n; ++i) {
            pos[m + 1] = i;
            for(; m >= 0 && heights[i] < hgt[m]; --m) {
                // cout<<hgt[m]<<":["<<pos[m]<<","<<i<<")\n";
                ans = max(ans, hgt[m] * (i - pos[m]));
            }
            hgt[++m] = heights[i];
        }
        return ans;
    }
};

## :memo: The Skyline Problem (Hard)


### 作法
這一題要用Divide and Conquer類似MergeSort的作法

// Divide-and-conquer algorithm to solve skyline problem, which is similar with the merge sort algorithm.
int** DC_getSkyline(int** buildings, int buildingsSize, int* returnSize) {
    *returnSize = 0;
    if (buildingsSize <= 0)
    {
        return 0;
    }

    int **ret;
    
    if (buildingsSize == 1)
    {
        ret = malloc(sizeof(int*) * 2);
        
        int *t = malloc(sizeof(int) * 2);
        t[0] = buildings[0][0];
        t[1] = buildings[0][2];
        ret[0] = t;   // 直接二維陣列assign給二維陣列
        
        t = malloc(sizeof(int) * 2);
        t[0] = buildings[0][1];
        t[1] = 0;
        ret[1] = t;
        
        *returnSize = 2;
        
        return ret;
    }
    
    int mid = buildingsSize / 2;
    int l_rsize = 0;
    
    int **l_ret = DC_getSkyline(buildings, mid, &l_rsize);

    int r_rsize = 0;
    int **r_ret = DC_getSkyline(buildings + mid, buildingsSize - mid, &r_rsize);
    
    //merge results
    ret = malloc(sizeof(int*) * (l_rsize + r_rsize));
    
    int lp = 0;
    int rp = 0;
    int lh = -1;
    int rh = -1;
    while (lp < l_rsize && rp < r_rsize)
    {
        int *l_pot = l_ret[lp];
        int *r_pot = r_ret[rp];
        if (l_pot[0] < r_pot[0]) 
        {
            lh = l_pot[1];
            l_pot[1] = lh > rh ? lh : rh;

            if (0 == *returnSize || l_pot[1] != ret[*returnSize - 1][1]) 
            {
                ret[*returnSize] = l_pot;
                ++(*returnSize);
            }
            else 
            {
                free(l_pot);
            }
            ++lp;
        } 
        else if (l_pot[0] > r_pot[0])
        {
            rh = r_pot[1];
            r_pot[1] = rh > lh ? rh : lh;

            if (0 == *returnSize || r_pot[1] != ret[*returnSize - 1][1])
            {
                ret[*returnSize] = r_pot;
                ++(*returnSize);
            }
            else
            {
                free(r_pot);
            }
            ++rp;
        } 
        else 
        {
            //equal x
            lh = l_pot[1];
            rh = r_pot[1];

            l_pot[1] = lh > rh ? lh : rh;
            if (0 == *returnSize || l_pot[1] != ret[*returnSize - 1][1])
            {
                ret[*returnSize] = l_pot;
                ++(*returnSize);
            }
            else
            {
                free(l_pot);
            }
            free(r_pot);
            ++lp;
            ++rp;
        }
    }
    
    //appending extra
    while (lp < l_rsize)
    {
        int *l_pot = l_ret[lp];
        if (0 == *returnSize || l_pot[1] != ret[*returnSize - 1][1])
        {
            ret[*returnSize] = l_pot;
            ++(*returnSize);
        }
        else
        {
            free(l_pot);
        }
        ++lp;
    }

    while (rp < r_rsize)
    {
        int *r_pot = r_ret[rp];
        if (0 == *returnSize || r_pot[1] != ret[*returnSize - 1][1])
        {
            ret[*returnSize] = r_pot;
            ++(*returnSize);
        }
        else
        {
            free(r_pot);
        }
        ++rp;
    }
    
    //free left and right middle result
    free(l_ret);
    free(r_ret);

    return ret;
}
int** getSkyline(int** buildings, int buildingsSize, int* buildingsColSize, int* returnSize, int** returnColumnSizes) {
    int** result = DC_getSkyline(buildings, buildingsSize, returnSize);
    
    *returnColumnSizes = (int*) malloc(sizeof(int) * (*returnSize));
    for (int i = 0; i < *returnSize; i++)
    {
        (*returnColumnSizes)[i] = 2;
    }
    
    return result;
}

## :memo: 刷題檢討
### 規則
1. function命名不能直接命名place()和remove()
2. **divide-and-conquer problem has a sole solution**
3. **backtracking problem has unknown number of solutions**.
4. 遞迴轉迭代要用stack或queue
5. 數字太大就不能用qsort，只能用自寫的Mergesort (C\)
### Divide and Conquer
0. 大function包住merge function
1. 通常是用大function去執行divide的操作(利用引數的range)
2. merge可能是2個大function的交集或聯集也可能是一個merge function，merge寫在大function程式碼最後末段
### Backtracking
1. 熟記Template
2. 回傳值如果不是要總方法數，如:布林值，那程式碼則要調整一些片段