77. Combinations

很基本的backtraking題目，用遞迴就可以解決的問題，題目不再多贅述。會刻意寫這篇是因為遇到相同複雜度情況下，在leetcode的執行環境下執行時間有很大的差距。

下面是我寫的第一版，每一個數字輪流當頭去排列，每新增一個數字就k-1，代表要取的數字就會少一個。但可以注意到這邊記憶體空間是可以再優化的，在優化前runtime約 512 ms，Memory space 佔用了222.44MB左右。

class Solution {
public:
    void recursion(int n, int k, int head, vector<int> element, vector<vector<int>> &result){
        element.push_back(head);
        if(k == 1){
            result.push_back(element);
        }
        else{
            for(int i=head+1; i<=n; i++)
                recursion(n, k-1, i, element, result);
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;

        for(int i=1; i<=n; i++){
            recursion(n, k, i, vector<int>(), result);
        }
        return result;
    }
};

下面的片段是優化後的程式碼，可以注意到其實element可以用call by reference 只是要在呼叫遞迴式前，需要把原本push進去的數字pop出來，避免往前遞移的時候，原本的不應該被算進去的數字被保留。

class Solution {
public:
    int n;
    void recursion(int k, int head, vector<int>& element, vector<vector<int>> &result){
        if(k == 1){
            element.push_back(head);
            result.push_back(element);
            element.pop_back();
        }
        else{
            for(int i=head+1; i<=n; i++){
                element.push_back(head);
                recursion(k-1, i, element, result);
                element.pop_back();
            }
        }
    }
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> element;
        this->n = n;
        for(int i=1; i<=n; i++){
            recursion(k, i, element, result);
        }
        return result;
    }
};

在優化後的執行時間變快了很多約13ms左右，而記憶體空間也只用了9MB左右，我猜測可能是為了複製element的參數，所以花了很多時間跟空間。