【遞歸+回溯】

三級位址選擇器引出的遞歸回溯方法

• 題目介紹
• • 題解
  • 回溯模闆
  • 拓展（leetcode17、22、46、77、79、78）

題目介紹

已知資料格式，實作一個函數 fn ，給一個 id 找對外連結條中其對應的所有的父級 name

示例1: 傳入 id ddrr2, 傳回 廣東省深圳市福田區A街道

示例2: 傳入 id sdsd, 傳回 廣東省深圳市

const cityData = [{
 id: 'axzx',
 name: '廣東省',
 children: [
   {
     id: 'sdsd',
     name: '深圳市',
     children: [
       {
         id: '45dss',
         name: '南山區'
       },
       {
         id: 'sdsd11',
         name: '福田區',
         children: [{
           id: 'ddrr2',
           name: 'A街道'
         }]
       }
     ]
   },
   {
     id: '2323d',
     name: '東莞市',
     children: [
       {
         id: 'xxs2',
         name: 'A區'
       },
       {
         id: 'kklio2',
         name: 'B區',
       }
     ]
   }
 ]
}];
           

題解

這是三級位址select元件最常用的算法，可以将數組結構看成一棵樹，然後用遞歸+回溯的方法做，首先可以思考遞歸出口以及每一層遞歸的函數傳參，這道題目遞歸出口有兩種情況：第一種找到了對應的id，第二種情況已經周遊到目前最後一層還沒找到。（第一種情況需要結束整個函數并return出結果，第二種情況需要結束目前遞歸并回到上一層狀态）

function search(id,data){
    // 1.遞歸函數
    function recurse(currentData){
        // 2. 遞歸出口
        if(currentData?.id===id) return;
        if(!currentData?.children) return;
        for(const v of currentData){
            recurse(v?.children);
        }
        
    }
    for(const v of data){
        recurse(v);  
    }
}
           

根據題意還需要一個res數組在每次遞歸時将目前周遊對象的name push進去，并且兩種遞歸出口後續操作完全不同，是以在代碼中新增一個res并且修改遞歸出口函數。

function search(id,data){
    let res = [];
    // 1.遞歸函數
    function recurse(currentData){
        // 2. 遞歸出口
        if(currentData?.id===id) return true;
        if(!currentData.children) return false;
        for(const v of currentData.children){
            res.push(v.name);
            const flag = recurse(v);
            if(flag){
                return true;
            }
            // 回溯
            res.pop();
        }
        
    }
    for(const v of data){
        res.push(v.name);
        const flag = recurse(v);
        if(flag){
            console.log(res);
            return res.join('');
        }
        // 回溯
        res.pop();
    }
}
           

回溯模闆

上述題目中當目前節點無子節點退出目前遞歸後需要執行回溯算法，回溯算法可以套用下面架構

function main(){
	function curse(){
		/*遞歸出口*/
		for(){
			/**狀态壓入*/
			curse();
			/**回溯，狀态推出 */
		}
	}
	curse(); 
}
           

拓展（leetcode17、22、46、77、79、78）

leetcode17 連結: 電話号碼的字母組合

leetcode22 連結: 括号生成

leetcode46 連結: 全排列

leetcode77 連結: 組合

leetcode78 連結: 子集

leetcode79 連結: 單詞搜尋

類似題目都可以去根據上述思路來做，先遞歸到最後一層節點，如果滿足題意，那麼直接return，如果不滿足，回溯到上一節點壓入另外的狀态繼續遞歸，直到滿足題目要求為止。注意遞歸中每一層的需要周遊哪些資料，比如電話号碼字母組合中的需要周遊目前數字的所有字母。

var letterCombinations = function(digits) {
	let matrix = ['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz'];
	function curse(i){
		/**出口 */
		for(const v of matrix[digits[i]]){
			/**狀态壓入 */
			curse(i+1);
			/**狀态pop*/
		}
	}
	curse(0)
};