本日寫遞迴~

46. Permutations

題目要求: 要求生成一個陣列的所有排列。
遞迴過程中，為避免重複使用數字，我們使用了一個 isUsed 布林陣列來標記每個數字是否已經被使用過。如果當前選取的數字未被使用，我們將其加入暫存陣列 tmp，並遞迴地繼續選取下一個數字。當選取的數字達到指定長度時，將結果存入最終的結果集 res 中。遞迴結束後，我們還需將該數字彈出以回溯到上一步，繼續其他未使用數字的選取過程

class Solution {
public:
    void dfs(int n, vector<int> &nums, vector<vector<int>> &res, vector<bool> &isUsed, vector<int> &tmp) {
        if (n == 0) {
            res.push_back(tmp);
            return;
        }
        for (int i = 0; i < nums.size(); i++) {
            if (isUsed[i] == false) {
                isUsed[i] = true;
                tmp.push_back(nums[i]);
                dfs(n-1, nums, res, isUsed, tmp);
                tmp.pop_back();
                isUsed[i] = false;
            }
        }
    
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<bool> isUsed(nums.size(), false);
        vector<int> tmp;
        dfs(nums.size(), nums, res, isUsed, tmp);
        return res;
    }
};

遞迴過程的時間複雜度為 O(n!)，因為每次排列涉及 n 個數字的排列組合

77. combinations

題目要求:
從 1 到 n 的數字中選出 k 個不同的數字進行組合。我們只需要選取特定數量的元素，而不是排列所有的元素。

遞迴函數在選取一個數字後，會繼續從剩下的數字中選取，直到選擇的數字數量達到 k 為止。當 k 等於 0 時，表示已經選取了足夠的數字，此時將當前的組合加入結果集中。這樣的遞迴方式同樣依賴深度優先搜索，不同的是每次選取後進入下一層遞迴時，我們只考慮未被選取的後續數字，避免了重複組合。

class Solution {
public:
    void dfs(int i, int n, int k, vector<vector<int>> &res, vector<int> &tmp) {
        if (!k) {
            res.push_back(tmp);
            return;
        }
        for (int j = i+1; j <= n; j++) {
            tmp.push_back(j);
            dfs(j, n, k-1, res, tmp);
            tmp.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> tmp;
        dfs(0, n, k, res, tmp);
        return res;
    }
};

時間複雜度為 O(C(n,k))，即選擇 k 個數字的組合數

62. Unique Paths

要求計算從左上角走到右下角的不同路徑數量。此題可以看作是典型的網格問題，每次只能向右或向下移動。

我們可以將問題轉化為遞迴的形式：每次向下或向右移動一步後，問題縮小為一個較小的子問題。如果我們已經到達了終點，即是一條路徑，故返回 1。如果無法再移動，則返回 0。

class Solution {
public:
    int uniquePaths(int m, int n) {
        if (m == 1 && n == 1) return 1;
        if (m < 1 || n < 1 ) return 0;
        return uniquePaths(m-1, n) + uniquePaths(m, n-1);
    }
};

時間複雜度: O(2^n)

這樣的遞迴方式會產生大量重複計算，因為相同的網格位置會被多次重複計算，因此明天將寫DP，使用陣列記錄重複出現狀態的答案。