今天的題單：

• Combination Sum

• Permutations

39. Combination Sum

給幾個數字，列出能共組出 target sum 的所有組合，數字的使用次數不限。

Example:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]

思路：backtracking，從 target 值開始用 DFS 遞迴的方式試所有的 candidates，為了保證不要找到重複的組合，限制一條搜尋路徑下的選擇都不能小於前者。

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> res;
        vector<int> comb;

        list_combination(res, candidates, comb, target, 0, candidates.size());

        return res;
    }

    void list_combination(vector<vector<int>>& res, vector<int>& candidates, vector<int>& comb, int target, int start, int end) {

        if (target == 0) {
            res.emplace_back(comb);
            return;
        } else if (target < 0) {
            return;
        }
        
        for (int i = start; i < end; i++) {
            comb.emplace_back(candidates[i]);
            list_combination(res, candidates, comb, target-candidates[i], i, end);
            comb.pop_back();
        }
    }
};

46. Permutations

列舉給定數字的所有的排列組合，數字都不相同。

思路：組合共有 n 個位置 （loc = 1 ~ n）。依序在 loc = i 依序填入所有數字，每填完一個數字後，就遞迴往下在 loc = i+1 繼續枚舉所有數字。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> comb(nums.size());
        vector<bool> used(nums.size(), false);

        list_combinations(res, comb, nums, used, 0);

        return res;
    }

    void list_combinations(vector<vector<int>>& res, vector<int>& comb, vector<int>& nums, vector<bool>& used, int loc) {
        
        if (loc == nums.size()) {
            res.emplace_back(comb);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            if (!used[i]) {
                comb[loc] = nums[i];
                used[i] = true;
                list_combinations(res, comb, nums, used, loc+1);
                used[i] = false;
            }
        }

    }
};

reference:

• https://web.ntnu.edu.tw/~algo/Backtracking.html

• https://bclin.tw/2021/08/06/leetcode-39/

休息再出發

堅持了 30 天，題目累積下來也寫了 60 題，把題單完成了 1/3。

題目總有解不出來的時候，這很正常，可能知道方法但是卡住，可能是根本不知道解法。從這些題目一點一點熟悉常用的演算法和資料結構，練習新的演算法，不知不覺寫題目這件事就不怎麼討厭了，甚至蠻有趣的，解完題目還會有成就感想要解下一題，有了好的正向回饋，也發現其實自己沒有想像中不擅長。

這大概就是做了才知道的道理吧，得到的結果超乎預期，這是一個月前沒有預料到的。

題單還有大半還沒寫，還有很多要學，旅途還沒結束，先做休息，之後繼續前進。