47. Permutations II
題目網址：https://leetcode.cn/problems/permutations-ii/
題意：給一含重複數的 array nums, 按任意順序返回所有不重複的排列。
Solution：
想法：類似 46. Permutations, 只是要排除掉相同數當頭e.g. [1, 1, 2]
1 當頭 : [1, 1, 2], [1, 2, 1]
1 當頭 : [1, 1, 2], [1, 1, 2]➔ 重複排列, 故要記住哪些數當過開頭, 若後面遇到做過開頭的數則不做 swap, 直接跳過
class Solution {public: vector<vector<int>> permuteUnique(vector<int>& nums) { dfs(nums, 0, nums.size()); return res; }private: vector<vector<int>> res; void dfs(vect ...
77. Combinations
題目網址：https://leetcode.cn/problems/combinations/
題意：給兩個整數 n 和 k, 以任意順序返回 [1, n] 中所有可能的 k 個數組合。
Solution：
想法：取每個 i 輪流當開頭, 其中 i 的範圍是 [1, n], 並從 [i + 1, n] 取 k - 1 個（從 i + 1 取必不會重複到前面）。dfs() 中的 for loop 是取 j + 1, 因為若取 i + 1, 則當 j > i + 1 後, 便會取到重複的組合。e.g. n = 3, k = 2, 其中 [1, 2], [2, 1] 不能同時出現
class Solution {public: vector<vector<int>> combine(int n, int k) { dfs(1, n, k); return res; }private: vector<int> cur; vector<vector<i ...
216. Combination Sum III
題目網址：https://leetcode.cn/problems/combination-sum-iii/
題意：找出所有相加之和為 n 的 k 個數的組合，且滿足下列條件：
只使用數字 1 到 9
每个數字最多使用一次
以任意順序返回所有可能的組合, 組合不能重複。
Solution：
想法：利用 DFS + Backtracking
class Solution {public: vector<vector<int>> combinationSum3(int k, int n) { dfs(k, n, 1); return res; }private: vector<int> cur; vector<vector<int>> res; void dfs(const int k, const int n, const int i){ if (k == 0 && n == 0) ...
320. Generalized Abbreviation
題目網址：https://leetcode.cn/problems/generalized-abbreviation/
題意：寫一函式來生成一個單字的通用縮寫, 以任意順序返回。
Solution 1：
想法：每個 char 都有「取縮寫 or 不取縮寫」兩種選擇, 其中用 num 代表在 word[i] 前面取縮寫的連續 char 數
取縮寫：i + 1, 且 num + 1, 並進入下一輪遞迴
不取縮寫：
若 num != 0：
將 num 加入到 cur 中, 並將 num 歸零
將 word[i] 加入到 cur 中, 並進入下一輪遞迴
若 num == 0：
將 num 歸零
將 word[i] 加入到 cur 中, 並進入下一輪遞迴
class Solution {public: vector<string> generateAbbreviations(string word) { string cur; dfs(word, 0, word.size(), cur, 0); ...
377. Combination Sum IV
題目網址：https://leetcode.cn/problems/combination-sum-iv/
題意：給一元素皆不同的array nums 和一整數 target, 返回總合為 target 的元素排列個數。
答案保證符合 32-bit 整數範圍（而非 32-bit 有號整數）
進階：如果 nums 中允許有負數, 需要向題目中添加哪些限制條件?
Solution 1：（TLE 無法通過）
想法：利用 DFS, 類似 39. Combination Sum
class Solution {public: int combinationSum4(vector<int>& nums, int target) { int res = 0; dfs(nums, target, res); return res; }private: void dfs(const vector<int>& nums, int& target, int&am ...