代碼隨想錄訓(xùn)練營第25天-回溯

216. 組合總和 III

找出所有相加之和為 n 的 k 個數(shù)的組合,且滿足下列條件:

只使用數(shù)字1到9
每個數(shù)字 最多使用一次
返回 所有可能的有效組合的列表 奶赔。該列表不能包含相同的組合兩次,組合可以以任何順序返回输虱。

示例 1:
輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
1 + 2 + 4 = 7
沒有其他符合的組合了。

class Solution {
private:
    vector<int> path;
    vector<vector<int>> result;
    void backTracking(int sum, int startIndex, int k, int target) {
        //cout << sum << " " << path.size() << " " <<k <<endl;
        if (path.size() == k && target == sum) {
            result.emplace_back(path);
            return;
        }

        if (path.size() >= k && target != sum) {
            return;
        }

        if (sum > target && path.size() <= k) {
            return;
        }

        for (int i = startIndex; i<= 9 - (k-path.size()) + 1; i++) {
            path.emplace_back(i);
            sum = sum + i;
            //cout << sum << endl;
            backTracking(sum, i+1, k, target);
            sum = sum -i ;
            path.pop_back();
        }
    }
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        path.clear();
        result.clear();
        backTracking(0, 1, k, n);
        return result;
    }
};

知識點:

套用回溯法套路即可脂凶。主要要把圖畫出來宪睹。
for循環(huán)要干什么,每次進(jìn)入迭代要干什么蚕钦、

void backtracking(參數(shù)) {
    if (終止條件) {
        存放結(jié)果;
        return;
    }
    for (選擇:本層集合中元素(樹中節(jié)點孩子的數(shù)量就是集合的大泻岜ぁ)) {
        處理節(jié)點;
        backtracking(路徑,選擇列表); // 遞歸
        回溯冠桃,撤銷處理結(jié)果
    }
}

17. 電話號碼的字母組合

給定一個僅包含數(shù)字 2-9 的字符串,返回所有它能表示的字母組合道宅。答案可以按 任意順序 返回食听。

給出數(shù)字到字母的映射如下(與電話按鍵相同)。注意 1 不對應(yīng)任何字母污茵。


200px-telephone-keypad2svg.png

示例 1:

輸入:digits = "23"
輸出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

class Solution {
private:
    string path;
    vector<string> result;
    const string letterMap[10] = {
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz"
    };
    void backTracking(string digits, int index) {
        if (index == digits.size()) {
            result.push_back(path);
            return;
        }
        int digit = digits[index] - '0';
        string letters = letterMap[digit];
        # for循環(huán)遍歷的是每一層的數(shù)據(jù)
        for (int i = 0 ; i< letters.size(); i++) {
            path.push_back(letters[i]);
            #迭代是進(jìn)入下一層的數(shù)據(jù)
            backTracking(digits, index+1);
            path.pop_back();
        } 
    }
public:
    vector<string> letterCombinations(string digits) {
        path.clear();
        result.clear();
        if (digits.size() == 0) {
            return result;
        }
        backTracking(digits, 0);
        return result;
    }
};

知識點

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末樱报,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子泞当,更是在濱河造成了極大的恐慌迹蛤,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件襟士,死亡現(xiàn)場離奇詭異盗飒,居然都是意外死亡,警方通過查閱死者的電腦和手機陋桂,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進(jìn)店門逆趣,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人嗜历,你說我怎么就攤上這事宣渗《端” “怎么了?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵痕囱,是天一觀的道長田轧。 經(jīng)常有香客問我,道長鞍恢,這世上最難降的妖魔是什么傻粘? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮有序,結(jié)果婚禮上抹腿,老公的妹妹穿的比我還像新娘。我一直安慰自己旭寿,他們只是感情好警绩,可當(dāng)我...
    茶點故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著盅称,像睡著了一般肩祥。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上缩膝,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天混狠,我揣著相機與錄音,去河邊找鬼疾层。 笑死将饺,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的痛黎。 我是一名探鬼主播予弧,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼湖饱!你這毒婦竟也來了掖蛤?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤井厌,失蹤者是張志新(化名)和其女友劉穎蚓庭,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體仅仆,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡器赞,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了墓拜。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片拳魁。...
    茶點故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖撮弧,靈堂內(nèi)的尸體忽然破棺而出潘懊,到底是詐尸還是另有隱情姚糊,我是刑警寧澤,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布授舟,位于F島的核電站救恨,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏释树。R本人自食惡果不足惜肠槽,卻給世界環(huán)境...
    茶點故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望奢啥。 院中可真熱鬧秸仙,春花似錦、人聲如沸桩盲。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽赌结。三九已至捞蛋,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間柬姚,已是汗流浹背拟杉。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留量承,地道東北人搬设。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像撕捍,于是被迫代替她去往敵國和親拿穴。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容