?77. 組合77. 組合77. 組合

給定兩個(gè)整數(shù)?n?和?k，返回范圍?[1, n]?中所有可能的?k?個(gè)數(shù)的組合。

你可以按?任何順序?返回答案。

思路：

如果解決一個(gè)問題有多個(gè)步驟，每一個(gè)步驟有多種方法，題目又要我們找出所有的方法，可以使用回溯算法；
回溯算法是在一棵樹上的 深度優(yōu)先遍歷（因?yàn)橐宜械慕猓孕枰闅v）；

為什么說是在一棵樹上的深度優(yōu)先遍歷呢？比如說，你現(xiàn)在要解決一個(gè)問題，這個(gè)問題被分為了若干的步驟，對(duì)于每一個(gè)步驟都有多個(gè)方法到下一個(gè)步驟。（聽君一席話，就是一席話，嘿嘿嘿?。。?。就是說我們么一個(gè)步驟的選擇都是可以返回來更換的。

就拿本題來說：

? ? ? ? 比如說給了4和3這兩個(gè)數(shù)據(jù)；我們要從1,2,3,4,這4個(gè)數(shù)里面取3個(gè)數(shù)。很容易分析出來：當(dāng)我們第一個(gè)數(shù)取1的時(shí)候，第二個(gè)數(shù)可以去2,3,4,.........。一次推下去。我們會(huì)得到一棵一棵的樹。樣子就是這個(gè)樣子（這個(gè)不是我畫的，我去LeetCode的題解上找到哈哈哈哈?。。?/p>

?想明白這個(gè)過程，那我們的解題辦法就來了。對(duì)于[1? n]里面的每一個(gè)數(shù)，在最后選擇的k個(gè)數(shù)里面的只有兩種狀態(tài)，要么它在，要么它不在。所以我們只需要去遍歷這n個(gè)數(shù)，然后用一個(gè)數(shù)組temp把放入最后結(jié)果的數(shù)記錄下來。由于我們是從小到大遍歷，所以當(dāng)我們把當(dāng)前元素在最后結(jié)果里面的記錄完以后，后面再記錄的結(jié)果就不會(huì)再包含當(dāng)前元素了。

class Solution {public:    //temp 用來存放每一個(gè)可能的結(jié)果    vector temp;    //最終結(jié)果    vector> ans;    //深度優(yōu)先遍歷    void dfs(int cur, int n, int k) {        // 剪枝：當(dāng)遍歷到底cur個(gè)數(shù)是，如果temp的元素個(gè)數(shù)s+剩余元素個(gè)數(shù)t> combine(int n, int k) {        dfs(1, n, k);        return ans;    }};

46. 全排列

思路：通過上一題，這一題理解起來就更方便了。全部排列順序，就是上面的那個(gè)圖，第二次先選擇了2以后還可以繼續(xù)選擇1；所以我們只需要把每次選取的元素交換到數(shù)組左邊，這樣就可以和上一題的流程一樣了，不過記住記住排列的時(shí)候，未選擇的元素都可以來占當(dāng)前cur的位置，由于我們將未選擇的元素都交換到cur的右邊，所以從cur遍歷一遍就可以了。就是這么簡(jiǎn)單，k默認(rèn)為n就可以了。

class Solution {public:    void dfs(vector>& res, vector& output, int cur, int len){        // 所有數(shù)都填完了        if (cur == len) {            res.emplace_back(output);            return;        }        //這里每一個(gè)數(shù)組右邊的數(shù)都可以當(dāng)做第cur個(gè)元素        for (int i = cur; i < len; ++i) {            // 動(dòng)態(tài)維護(hù)數(shù)組，將未選取的元素交換到數(shù)組右邊            swap(output[i], output[cur]);            // 繼續(xù)遞歸填下一個(gè)數(shù)            dfs(res, output, cur + 1, len);            // 撤銷交換操作            swap(output[i], output[cur]);        }    }    vector> permute(vector& nums) {        vector > res;        dfs(res, nums, 0, (int)nums.size());        return res;    }};

784. 字母大小寫全排列

給定一個(gè)字符串S，通過將字符串S中的每個(gè)字母轉(zhuǎn)變大小寫，我們可以獲得一個(gè)新的字符串。返回所有可能得到的字符串集合。

思路： 注意理解題目要求，題目是說每個(gè)子母可以進(jìn)行大小寫變換，但是沒有說可以改變位置哦。

class Solution {public:    void dfs(vector &res,int cur,string &s,int len){        //數(shù)字不變        while(cur= "0" && s[cur] <= "9")            cur++;        if(cur == len){            res.emplace_back(s);            return ;        }            //子母轉(zhuǎn)變大小寫        if(s[cur]>="a"&&s[cur]<="z")            s[cur] = toupper(s[cur]);        else            s[cur] = tolower(s[cur]);        dfs(res,cur+1,s,len);        //子母不轉(zhuǎn)變大小寫        if(s[cur]>="a"&&s[cur]<="z")            s[cur] = toupper(s[cur]);        else            s[cur] = tolower(s[cur]);        dfs(res,cur+1,s,len);    }    vector letterCasePermutation(string s) {        vector res;        int len = s.length();        dfs(res,0,s,len);        return res;    }};

蕪湖~~~~~~~~~