弱小和無知不是生存的障礙,傲慢才是  --《三體·死神永生》

大家好,我是「柒八九」

今天,我們繼續探索JS算法相關的知識點。我們來談談關於「回溯法」的相關知識點和具體的算法。

如果,想了解其他數據結構的算法介紹,可以參考我們已經發布的文章。如下是算法系列的往期文章。

文章list

  1. 整數
  2. 常規排序算法
  3. 數組
  4. 字符串
  5. 鏈表
  6. 隊列
  7. 二叉樹

好了,天不早了,乾點正事哇。function subsets(nums){
  let result = [];
  if(nums.length == 0return result;
  
  (function helper(nums,index,subset,result){
    if(index === nums.length){ // 基線條件
      result.push([...subset])
    }else if(index < nums.length){
      helper(nums,index + 1, subset,result); // 不將數字添加到子集
      
      subset.push(nums[index]); // 將數字添加到子集中
      helper(nums,index + 1,subset,result);
      subset.pop();
    }
  })(nums,0,[],result)
  return result;
}

代碼解釋

  1. 遞歸函數helper有四個參數
    1. nums 是數組nums,包含輸入集合的所有數字。可以逐一從集合中「取出一個數字並選擇是否將數字添加到子集中」
    2. index是當前取出的數字在數組nums中下標
    3. subset「當前子集」
    4. result「所有已經生成」的子集
  2. 每當從數組nums中取出一個下標為index的數字時,都要考慮是否將該數字添加到子集subset中。
    1. 「不將數字添加到子集的情形」。不對子集進行任何操作,只需要「調用遞歸函數helper處理數組nums中的下一個數字(下標增加1)」
      1. helper(nums,index + 1, subset, result)
    2. 「將下標為index的數字添加到子集subset中」
      1. 在將該數字添加到子集之後
        1. subset.push(nums[index])
      2. 接下來調用遞歸函數處理數組nums下一個數字(下標增加1)‍
        1. helper(nums,index + 1, subset, result)
      3. 「等遞歸函數執行完成之後,函數helper也執行完成,接下來將回溯到前一個數字的函數調用處繼續執行。」
        1. 在回溯到父節點之前,應該「清除」已經對子集狀態進行的修改。
        2. subset.pop()
  3. 「當index等於數組nums的長度時候」,表示數組中的所有數字都已經處理過,因此可以生成一個子集。將子集subset添加到result
    • 在此處加入的是subset的副本,因為接下來還需要修改subset用以獲得其他的子集
    • result.push([...subset])

包含k個元素的組合

題目描述:

輸入nk,請輸入從1n中選取k個數字組成的所有「組合」

輸入:n = 3, k = 2
輸出:[[1,2],[1,3],[2,3]]

分析

  1. 集合的組合也是一個子集,求集合的組合的過程和求子集的過程是一樣的。
  2. 此題增加了一個限制條件,只找包含k個數字的組合
  3. 在上一個題目「所有子集」增加一些限定條件,就可以處理該題。

代碼實現

function combine(n,k){
 let result = [];
 (function helper(n,k,index,subset,result){
   if(subset.length === k){ // 基線條件
     result.push([...subset])
   }else if(index <= n){
     helper(n,k, index + 1, subset,result); // 不將數字添加到子集
     
     subset.push(index); // 將數字添加到子集中
     helper(n,k,index + 1,subset,result); 
     subset.pop();
   }
 })(n,k,1,[],result)
 return result;
}

代碼解釋

  1. 遞歸函數helper有五個參數
    1. n 是數組範圍1~n
    2. k是組合的長度
    3. index是當前取出的數字
    4. subset是當前子集
    5. result是所有「已經生成」的子集
  2. subset.length等於k時,進行子集的收集處理
    • result.push([...subset])
  3. 還有一點 index是從1開始的。

允許重複選擇元素的組合

題目描述:

給定一個「沒有重複數字」的正整數集合,請找出所有元素之和等於某個給定值(target)的所有組合。
同一個數字可以在組合中「重複任意次」

輸入:candidates = [2,3,6,7], target = 7
輸出:[[7],[2,2,3]]

分析

  1. 關於組合的相關題目,使用「回溯法」解決
  2. 用回溯法解決的問題都能夠「分成若干步來解決,每一步都面臨著若干選擇」
  3. 對於從集合中選取數字組成組合的問題而言,集合中有多少個數字,解決這個問題就需要多少步。
  4. 每一步從集合中取出一個下標為i的數字,此時,「面臨兩個選擇」
    1. 「什麼都不做」 --選擇「跳過這個數字」不將該數字添加到組合中,接下來處理下標為i + 1的數字。
    2. 「將數字添加到組合中」 -- 由於一個數字可以重複在組合中「重複出現」,也就是下一步「可能再次選擇同一個數字」,因此下一步仍然處理下標為i的數字。

代碼實現

function combinationSum(nums,target){
  let result = [];
  (function helper(nums,target,index,subset,result){
    if(target ==0){ //基線條件
      result.push([...subset])
    }else if(target > 0 && index < nums.length){
      helper(nums,target,index + 1,subset,result); // 不將數字添加到子集
      
      subset.push(nums[index]); // 將數字添加到子集中
      helper(nums,target - nums[index],index,subset,result);
      subset.pop();
    }
  })(nums,target,0,[],result)
  return result;
}

代碼解釋

  1. 由於nums[index]可能在組合中「重複出現」,因此在index處,「選擇了將數字添加到組合」的選擇,「遞歸調用helper時,index是不需要+1的」
  2. 每當選擇了一個數據後,需要更新target
    • target - nums[index]
  3. 當某次遍歷的時候,target0時,說明現在「子集」已經滿足情況。
    • result.push([...subset])
  4. 由於題幹中,數據都是「正整數」,在操作過程中,target只能少,不能多,所以可以判斷target0的關係,來進行「剪枝」處理。
    • if(target>0 && index < nums.length)

舉一反三

上面的幾個題目都是關於數學上的組合、集合,其實這些「模型」可以應用到很多其他問題中。

例如,當客人走近餐廳準備吃飯,一種點菜的方法就是生成一個符合條件的組合。

  • 如果每道菜「只點一份」,那麼就是找出「所有」符合條件的組合
  • 如果總共「只能點k道菜」,那麼就是找出「包含k個元素」的所有符合條件的組合
  • 如果每道菜可以「點任意多份」,那麼就是找出「允許選擇重複元素」的符合條件的組合

包含重複元素集合的組合

題目描述:

給定一個可能「包含重複數字」的整數集合,請找出所有元素之和等於某個給定值(target)的所有組合。
輸出中不得包含重複的組合。

輸入:candidates = [2,5,2,1,2], target = 5
輸出:[[1,2,2],[5]]

分析

  1. 如果輸入的集合中有重複的數字,不經過特殊處理將產生重複的組合。
  2. 避免重複的組合的方法是「當在某一步決定跳過某個值為m的數字時,跳過所有值為m的數字。」
  3. 為了方便跳過後面所有值相同的數字,可以「將集合中的所有數字排序,把相同的數字放在一起」,這樣方便比較數字。
    • 當決定「跳過某個值」時,可以按順序掃描後面的數字,「直到找到不同的值為止」

代碼實現

function combinationSum(nums,target){
  nums.sort((a,b) => a -b);
  
  let result = [];
  (function helper(nums,target,index,subset,result){
    if(target == 0){ // 基線條件
      result.push([...subset]);
    }else if(target > 0 && index < nums.length){
      // 選擇跳過某批值相同的數字
      helper(nums,target,getNext(nums,index),subset,result); 
      
      subset.push(nums[index]);
      helper(nums,target - nums[index], index + 1,subset,result);
      subset.pop();
    }
  })(nums,target,0,[],result)
  return result;
}

輔助函數

function getNext(nums,index){
  let next = index;
  while(next < nums.length && nums[next] == nums[index]){
    next++;
  }
  return next;
}

代碼解釋

  1. 排序是為了方便跳過相同的數字。
    • 這個處理方式和在數組中處理「三數之和」的道理是一樣的
  2. 利用getNext找到與當前index值不同的下標

沒有重複元素集合的全排列

題目描述:

給定一個「沒有重複數字」的集合,請找出它的所有全排列。

輸入:nums = [0,1]
輸出:[[0,1],[1,0]]

分析

  1. 排列和組合(子集)不同,排列「與元素的順序相關」,交互數字能夠得到不同的排列。
  2. 生成全排列的過程,就是「交換輸入集合中元素的順序以得到不同的排列」
  3. 如果輸入的集合有n個元素,
    • 那麼生成一個全排列需要n
    • 當生成排列的第一個數字時,面臨著n個選項
    • 當生成排列的第二個數字時,面臨著n-1個選項
  4. 解決「問題可以分成n步,每一步面臨著若干選項」  -- 「回溯法」

代碼實現

function permute(nums){
  let result = [];
  (function helper(nums,index,result){
    if(index == nums.length){
      result.push([...nums]) // 基線條件
    }else {
      for(let j = index;j        swap(nums,index,j); // 數字替換位置
        helper(nums,index + 1,result);
        swap(nums,index,j); // 清除對排列狀態的修改
      }
    }
  })(nums,0,result)
  return result;
}

輔助函數

const swap = (nums,i,j) => [nums[i],nums[j]] = [nums[j],nums[i]];

代碼解釋

  1. 在函數執行過程「總數組nums保存著當前排列的狀態」
  2. 當函數helper生成排列的下標為index的數字時,
    • 下標從0index-1的數字都「已經選定」
    • 但數組nums中下標從indexn-1的數字(假設數組的長度為n)都有可能放到排列的下標為index的位置
    • 因此函數helper「有一個for循環逐一用下標為index的數字交互它後面的數字」
    • for循環包含下標為index的數字本身,因為它自己也能放在排列下標為index的位置
    • swap(nums,index,j)
  3. 交互之後接著調用遞歸函數生成排列中下標為index + 1的數字
    • helper(nums,index + 1, result)
  4. 在函數退出之前需要「清除對排列狀態的修改」
    • swap(nums,index,j)

包含重複元素集合的全排列

題目描述:

給定一個包含「重複數據」的集合,請找出它的所有全排列

輸入:nums = [1,1,2]
輸出:[[1,1,2],[1,2,1],[2,1,1]]

分析

  1. 如果集合中有重複的數字,那麼「交換集合中重複的數字得到的全排列是同一個全排列」
  2. 當處理到全排列的第i個數字時,如果已經將某個值為m的數字交換為排列的第i個數字,那麼再遇到其他值為m的數字就「跳過」

代碼實現

function permuteUnique(nums){
  let result = [];
  (function helper(nums,index,result){
    if(index === nums.length){
      result.push([...nums]); // 基線條件
    }else {
      let map = {};
      for(let j = index;j        if(!map[nums[j]]){
          map[nums[j]] = true;
          
          swap(nums,index,j);
          helper(nums,index + 1,result);
          swap(nums,index,j);
        }
      }
    }
  })(nums,0,result)
  return result;
}

輔助函數

const swap = (nums,i,j) => [nums[i],nums[j]] = [nums[j],nums[i]];

代碼解釋

  1. 用一個「對象map,來保存已經交換到排列下標為index的位置的所有值」
  2. 只有當一個數值之前沒有被交換到第index位時才做交換,否則直接跳過
    • for循環中多一層判斷
    • if(!map[nums[j]])

解決其他問題

除了可以解決與集合排列、組合相關的問題,回溯法還能解決很多問題。

如果解決一個問題需要「若干步驟」,並且每一步都面臨「若干選擇」,當在「某一步」做了某個選擇之後,前往下一步仍然面臨若干選項。那麼可以考慮用「回溯法」

通常,回溯法可以用「遞歸代碼」實現。

生成匹配的括號

題目描述:

輸入一個正整數n,請輸出「所有」包含n個左括號和n個右括號的組合,要求每個組合的左括號和右括號匹配。

輸入:n = 3
輸出:["((()))","(()())","(())()","()(())","()()()"]

分析

  1. 輸入n,生成的括號組合包含n個左括號和n個右括號。
    • 因此,生成這樣的組合需要2n步,每一步生成一個括號
    • 「每一步都面臨著兩個選項」,既可能生成左括號也可能生成右括號
    • 「回溯法」解決
  2. 生成括號組合時,需要注意每一步都需要滿足兩個限制條件
    1. 左括號或右括號的數目不能超過n
    2. 括號匹配原則:即在「任意步驟」中已經生成的右括號的數目不能超過左括號的數目

代碼實現

function generateParenthesis(n){
  let result = [];
  (function helper(left,right,subset,result){
    if(left == 0 && right ==0){
      result.push(subset); //基線條件
      return ;
    }
    // 已經生成的左括號的數目少於`n`個
    if(left > 0){ 
      helper(left -1,right,subset + "(",result)
    }
    // 已經生成的右括號的數目少於已經生成的左括號的數目
    if(left < right){ 
      helper(left,right -1,subset + ")",restule)
    }
  })(n,n,"",result)
  return result;
}

代碼解釋

  1. 參數left:表示「還需要生成」的左括號的數目
  2. 參數right:表示「還需要生成」右括號的數目。
  3. 每生成一個左括號,參數left-1;每生成一個右括號,參數right -1;當left/right都等於0,一個完整的括號組合生成
    • result.push(subset);
  4. 在生成一個括號時
    • 只要「已經生成的左括號的數目少於n個」(left>0)就能生成一個左括號
    • 只要「已經生成的右括號的數目少於已經生成的左括號的數目」left < right)就能生成一個右括號

分割回文字符串

題目描述:

輸入一個字符串,要求將它「分割成若干子字符串,使每個字符串都是迴文」

輸入:s = "aab"
輸出:[["a","a","b"],["aa","b"]]

分析

  1. 當處理到字符串中的某個字符串時候,如果包括該字符在內後面還有n個字符,那麼面臨n個選項
    • 分割出長度為1的字符串(只包含該字符)
    • 分割出長度為2的字符串(包含該字符及它後面的一個字符)
    • 分割出長度為x的字符串 (x)
    • 分割出長度為n的字符串
  2. 解決這個問題需要很多步,每一步分割出一個迴文字符串。

代碼實現

function partition(str){
  let result = [];
  (function heler(str,start,subset,result){
    if(start == str.length){
      result.push([...subset]); // 基線條件
    }else {
      for(let i = start;i        if(isPalinadrome(str,start,i)){
          subset.push(str.substring(start,i+1));
          helper(str,i + 1,subset,result);
          subset.pop();
        }
      }
    }
  })(str,0,[],result)
  return result;
}

輔助函數

function isPalinadrome(str,start,end){
  while(start < end){
    if(str[start++]!=str[end--]) return false;
  }
  return true
}

代碼解釋

  1. 當處理到下標為start的字符串時,用一個for循環逐一判斷從下標start開始到i結束的每個子字符串是否會迴文
    • i從下標start開始,到字符串s的最後一個字符結束
  2. 如果是迴文,就分割出一個符合條件的子字符串,添加到subset
    • subset.push(str.substring(start,i+1))substring它的第一個參數表示子字符串的開始位置,第二個位置表示結束位置--返回結果不含該位置)
    • 接著處理下標從i+1開始的剩餘字符串。

小結

如果解決一個問題需要若干步驟,並且在每一步都面臨著若干選項,那麼可以嘗試用「回溯法」解決問題。

應用回溯法能夠解決「集合的排列、組合」的很多問題。

回溯法都可以使用「遞歸」的代碼實現。遞歸代碼需要先確定「遞歸退出」的邊界條件(基線條件),然後逐個處理集合中的元素。

對於「組合類」問題,每個數字都面臨兩個選項

  1. 添加當前數字到組合中
  2. 不添加當前數字到組合中

對於「排列類」問題,一個數字如果後面有n個數字,那麼面臨n+1個選擇,即可以將數字和後面的數字(包括它自身)交換。


後記

「分享是一種態度」

參考資料:劍指offer/leetcode官網/學習JavaScript數據結構與算法第3版

「全文完,既然看到這裡了,如果覺得不錯,隨手點個贊和“在看”吧。」


  • subset.push(nums[index])