77. 组合

分析搜索起点的上界进行剪枝
事实上，如果 n = 7, k = 4，从 5 开始搜索就已经没有意义了，这是因为：即使把 5选上，后面的数只有 6和 7，一共就 3个候选数，凑不出 4 个数的组合。
搜索起点的上界 + 接下来要选择的元素个数 - 1 = n
其中，接下来要选择的元素个数 = k - path.size()，整理得到：搜索起点的上界 = n - (k - path.size()) + 1
https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/

  1. var combine = function(n, k) {
  2.   let result=[]
  3.   let path=[]
  4.   function tranverse(startIndex){
  5.     if(path.length===k){ //回溯终止条件
  6.       result.push([...path])
  7.       return;
  8.     }
  9.     //耗时太久，需要剪枝优化，建议画图
  10.     for(let i=startIndex;i<=n-k+path.length+1;i++){
  11.       path.push(i)
  12.       tranverse(i+1) 
  13.       path.pop() //回溯撤销处理
  14.     }
  15.   }
  16.   tranverse(1);
  17.   return result;
  18. };

17. 电话号码的字母组合

  1. /**
  2.  * @param {string} digits
  3.  * @return {string[]}
  4.  */
  5. var letterCombinations = function(digits) {
  6.    let result=[]
  7.    const length= digits.length
  8.    if(length<1) return []
  9.    const letters=[
  10.        "abc",
  11.        "def",
  12.        "ghi",
  13.        "jkl",
  14.        "mno",
  15.        "pqrs",
  16.        "tuv",
  17.        "wxyz",
  18.    ]
  19.    let path=""
  20.    function tranverse(startIndex,path){
  21.        if(path.length===length){
  22.            result.push(path)
  23.            return;
  24.        }
  25.        const letter=letters[digits[startIndex]-2]
  26.        for(let j=0;j<letter.length;j++){
  27.           tranverse(startIndex+1,path+letter[j])
  28.        }
  29.    }
  30.    tranverse(0,path)
  31.    return result;
  32. };

131. 分割回文串

与复原IP地址类似，加入path前都有一定的校验。

  1. /**
  2.  * @param {string} s
  3.  * @return {string[][]}
  4.  */
  5. var partition = function(s) {
  6.   let result=[];
  7.   let path=[];
  8.   function backtracking(startIndex){
  9.      if(startIndex > s.length-1){
  10.         result.push([...path])
  11.         return;
  12.      }
  13.      for(let i=startIndex;i<s.length;i++){
  14.          let str=s.substr(startIndex,i-startIndex+1)
  15.          if(isPalindrome(str)) {
  16.             path.push(str) 
  17.             backtracking(i+1)
  18.             path.pop() 
  19.          }else{
  20.              continue;
  21.          }
  22.      } 
  23.   }
  24.   backtracking(0)
  25.   return result;
  26. };
  28. var isPalindrome =function(s){
  29.     let left=0,right=s.length-1
  30.     while(left<right){
  31.         if(s[left]!==s[right]){
  32.             return false
  33.         }
  34.         left++;
  35.         right--;
  36.     }
  37.     return true;
  38. }

93. 复原 IP 地址

与分割回文串类似，加入path前都有一定的校验。

  1. /**
  2.  * @param {string} s
  3.  * @return {string[]}
  4.  */
  5. var isValid=function(s){
  6.     if(s.length>1 && s[0]==='0') return false;
  7.     if(Number(s)>255) return false;
  8.     return true;
  9. }
  10. var restoreIpAddresses = function(s) {
  11.     let result=[]
  12.     let path=[]
  13.     function backtracking(startIndex){
  14.        if(path.length===4 && startIndex>s.length-1){     
  15.            if(startIndex>s.length-1){
  16.               result.push(path.join('.'));
  17.            }
  18.            return
  19.        }
  20.        for(let i=startIndex;i<s.length;i++){
  21.            let str=s.substr(startIndex,i-startIndex+1)
  22.            if(isValid(str)){
  23.                path.push(str)
  24.                backtracking(i+1)
  25.                path.pop()
  26.            }
  27.        }
  28.     }
  29.     backtracking(0)
  30.     return result;
  31. };

78. 子集

与组合的区别：组合取叶子节点，子集取每个节点
image.png

  1. var subsets = function(nums) {
  2.     //组合取叶子节点，子集取每个节点
  3.    function backtracking(startIndex){
  4.        result.push([...path])
  5.        for(let i=startIndex;i<nums.length;i++){
  6.            path.push(nums[i])
  7.            backtracking(i+1)
  8.            path.pop()
  9.        }
  10.    }
  11.    let result=[],path=[];
  12.    backtracking(0)
  13.    return result;
  14. };

90. 子集 II

与子集①相比，需要使用used来判断同一层是否用过相同数字，来去重。
如果用set来判断的话，空间复杂度和时间复杂度更高。
image.png

  1. /**
  2.  * @param {number[]} nums
  3.  * @return {number[][]}
  4.  */
  5. var subsetsWithDup = function(nums) {
  6.   let result=[],path=[];
  7.   let used=new Array(nums.length).fill(false);
  8.   nums.sort((a, b) => a - b);
  9.   function backtracking(startIndex){
  10.      result.push([...path])
  11.      for(let i=startIndex;i<nums.length;i++){
  12.           if(i>0 && nums[i]===nums[i-1] && !used[i-1]) continue;
  13.           used[i]=true;
  14.           path.push(nums[i])
  15.           backtracking(i+1)
  16.           used[i]=false;
  17.           path.pop()
  18.      }
  19.   }
  20.   backtracking(0)
  21.   return result;
  22. };

46. 全排列

和组合的区别是：

  • 每层都是从0开始搜索而不是startIndex

  • 需要used数组记录path里都放了哪些元素了

    1. /**
    2. * @param {number[]} nums
    3. * @return {number[][]}
    4. */
    5. var permute = function(nums) {
    6.   let result=[],used=[],path=[];
    7.   function backtracking(used,path){
    8.       if(path.length===nums.length) {
    9.           result.push([...path])
    10.           return;
    11.       }
    12.       for(let i=0;i<nums.length;i++){
    13.       const num=nums[i];
    14.       if(used[i]){
    15.           continue;
    16.       }
    17.       used[i]=true;
    18.       path.push(num);
    19.       backtracking(used,path);
    20.       path.pop();
    21.       used[i]=false;
    22.       }
    24.   } 
    25.   backtracking(used,path)
    26.   return result;
    27. };

    47. 全排列 II

需要去重，和子集②的去重的方法类似。

  1. var permuteUnique = function(nums) {
  2.   let result=[],path=[];
  3.   let used=new Array(nums.length-1).fill(false)
  4.   function backtracking(array){
  5.     if(path.length===array.length){
  6.         result.push([...path])
  7.         return;
  8.     }
  9.     for(let i=0;i<array.length;i++){
  10.         if(used[i]) continue; //全排列因为从0开始，需要对同一枝是否用过判断
  11.         if(i>0 && array[i-1]===array[i] && !used[i-1]){
  12.           continue; //used[i-1]为false说明同层相等数在之前用过了,为true表示是同一枝
  13.         }  
  14.         used[i]=true;  
  15.         path.push(array[i])
  16.         backtracking(array)
  17.         path.pop();
  18.         used[i]=false;  
  19.     }
  20.   }
  21.   nums.sort((a, b) => a - b);
  22.   backtracking(nums)
  23.   return result;
  24. };

22. 括号生成

  1. /**
  2.  * @param {number} n
  3.  * @return {string[]}
  4.  */
  5. var generateParenthesis = function(n) {
  6.    //剩余左括号的数量必须小于剩余右括号的数量
  7.    //回溯
  8.    function backtracking(path,l,r){
  9.       if(l===0 && r===0){
  10.           result.push(path);
  11.           return;
  12.       }
  13.       if(l===r)backtracking(path+"(",l-1,r) 
  14.       if(l<r) {
  15.         if(l>0) backtracking(path+"(",l-1,r)
  16.         backtracking(path+")",l,r-1)
  17.       }
  18.    }
  19.    let result=[],path="";
  20.    backtracking(path,n,n)
  21.    return result;
  22. };

51. N 皇后

  1. /**
  2.  * @param {number} n
  3.  * @return {string[][]}
  4.  */
  6. var isValid=function(row,column,dp){
  7.     const n=dp.length;
  8.     for(let r=0;r<row;r++){
  9.         if(dp[r][column]==='Q') return false;
  10.     }
  11.     for(let r=row-1,c=column-1;r>=0 && c>=0;r--,c--){
  12.         if(dp[r][c]==='Q') return false;
  13.     }
  14.     for(let r=row-1,c=column+1;r>=0 && c<n;r--,c++){
  15.         if(dp[r][c]==='Q') return false;
  16.     }
  17.     return true;
  18. }
  19. var solveNQueens = function(n) {
  20.   let result=[];
  21.   let dp=new Array(n).fill([]).map(() => new Array(n).fill('.'))
  22.   function backtracking(row){  
  23.     if(row===n){
  24.         result.push(dp.map((i)=>{return i.join('')}))
  25.         return;
  26.     }
  27.     for(let j=0;j<n;j++){
  28.         if(!isValid(row,j,dp)) continue;
  29.         dp[row][j]='Q'
  30.         backtracking(row+1);
  31.         dp[row][j]='.'
  32.     }   
  33.   }
  34.   backtracking(0)
  35.   return result;
  36. };

组合总和1

  1. var combinationSum = function (candidates, target) {
  2.     let result = [], path = [];
  3.     candidates.sort((a, b) => a - b);//不要写成candidates.sort()，这是默认从高到低
  4.     function backtracking(startIndex, sum) {
  5.         if (sum === target) {
  6.             result.push([...path])
  7.             return
  8.         }
  9.         for (let i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) { //需要剪枝
  10.             path.push(candidates[i])
  11.             backtracking(i, sum + candidates[i])
  12.             path.pop()
  13.         }
  14.     }
  15.     backtracking(0, 0)
  16.     return result;
  17. };

组合总和2
与上题不同的点：
1、candidates 中的每个数字在每个组合中只能使用 一次 。即要传入startIndex
2、解集不能包含重复的组合。需要排序+used保证同级没有重复数字

  1. var combinationSum2 = function (candidates, target) {
  2.     let result = []
  3.     let path = [];
  4.     candidates.sort((a, b) => a - b);
  5.     let used = Array(candidates.length).fill(false)
  6.     function backtracking(startIndex, sum) {
  7.         if (sum === target) {
  8.             result.push([...path])
  9.             return;
  10.         }
  11.         for (let i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
  12.             if (i > 0 && candidates[i] === candidates[i - 1] && !used[i - 1]) {
  13.                 continue
  14.             }
  15.             used[i] = true;
  16.             path.push(candidates[i])
  17.             backtracking(i + 1, sum + candidates[i])
  18.             path.pop();
  19.             used[i] = false;
  20.         }
  21.     }
  22.     backtracking(0, 0)
  23.     return result;
  24. };

组合总和3
这题和77.组合类似，是组合总和中最简单的一题。

  1. var combinationSum3 = function (k, n) {
  2.     let result = []
  3.     let path = []
  4.     function backtracking(startIndex, sum) {
  5.         if (path.length === k && sum === n) {
  6.             result.push([...path])
  7.             return;
  8.         }
  9.     if (path.length >= k) return;
  10.         for (let i = startIndex; i <= 9 && sum + i <= n; i++) {
  11.             path.push(i)
  12.             backtracking(i + 1, sum + i)
  13.             path.pop();
  14.         }
  15.     }
  16.     backtracking(1, 0);
  17.     return result;
  18. };

组合总和 Ⅳ

这道题用回溯会爆栈，代码和组合总和I一样

  1. var combinationSum4 = function (nums, target) {
  2.     let result = [], path = [];
  3.     nums.sort((a, b) => a - b);
  4.     function backtracking(sum) {
  5.         if (sum === target) {
  6.             result.push([...path])
  7.             return;
  8.         }
  9.         for (let i = 0; i < nums.length && sum + nums[i] <= target; i++) {
  10.             path.push(nums[i]);
  11.             backtracking(sum + nums[i]);
  12.             path.pop();
  13.         }
  14.     }
  15.     backtracking(0)
  16.     return result.length;
  17. };

image.png
怎么还可以用动态规划？噢因为这道题求总数，而不要求具体的结果，所以不必用回溯。
记住！求结果数量时想到动态规划，相当于回溯+备忘录。而求具体组合结果时必须用回溯穷举了。

  1. //怎么还可以用动态规划？？
  2. var combinationSum4 = function(nums, target) {
  3.   //完全背包,排列方案总和，需要累加
  4.    let dp=Array(target+1).fill(0);
  5.    dp[0]=1;
  6.    for(let i=1;i<=target;i++){
  7.        for(let j=0;j<nums.length;j++){
  8.            if(nums[j]>i) continue;
  9.            dp[i]=dp[i]+dp[i-nums[j]]
  10.        }
  11.    }
  12.    return dp[target];
  13. };

140. 单词拆分 II

与单词拆分①的区别：不求具体结果的用动规，求具体穷举结果的用回溯。
这题无限使用

  1. var wordBreak = function (s, wordDict) {
  2.     let result = [], path = []
  3.     var backtracking = function (startIndex) {
  4.         if (startIndex === s.length) {
  5.             result.push(path.join(" "));
  6.             return;
  7.         }
  8.         for (let i = 0; i < wordDict.length; i++) {
  9.             if (s.substr(startIndex, wordDict[i].length) === wordDict[i]) {
  10.                 path.push(wordDict[i]);
  11.                 backtracking(startIndex + wordDict[i].length)
  12.                 path.pop();
  13.             }
  15.         }
  16.     }
  17.     backtracking(0)
  18.     return result;
  19. };