按标签刷Leetcode也有一段时间了，本周轮到回溯算法，因此作一个适时的输出。

概念

回溯法，顾名思义，在找解的过程中需要掉回头重新找的。与之对应的是贪心算法或动态规划，贪心算法与动态规划都需要在子结构中找到最优解以进行下一步求解。
通常求解问题脑子第一想法也是用穷举来暴力求解，若不满足题目约束条件，换一条路重新穷举。换路的过程就是回溯了，概念比较容易理解。

Wiki概念：回溯法是一种可以找出所有（或一部分）解的一般性算法，尤其适用于约束满足问题（在解决约束满足问题时，我们逐步构造更多的候选解，并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解，转而测试其他的部分候选解）。这种傻瓜式试错的思想通常用递归来实现，在树与图的结构里也被称为深度优先搜索。
在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

LeetCode之回溯

254.Factor Combinations
给定正整数N，给出其能分解出的因子的所有组合。
1.因子不能为非1和自身
2.因子按升序排列
3.每个组合中因子的乘积等于N
input: 32
output:
[ [2, 16], [2, 2, 8], [2, 2, 2, 4], [2, 2, 2, 2, 2], [2, 4, 4], [4, 8] ]

一开始的思路：

  1. i从2到N-1遍历，若为N因子，则加入临时解，当前数变为N/i;若不是N因子，则跳过
  2. 找到解条件：当前搜索中数为1，则加入最终解中；
  3. 推出临时解最后一个因子，回溯至下一个i+1 因子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var factorCombinations = function (n) {
  var res=[],cur=n,tmp=[];
  factorHelp(cur,tmp,res);
  return res;
};

var factorHelp = function (cur,tmp,res) {
  if(cur==1) {
    res.push(tmp.slice(0));
  } else {
    for(i=2;i<=cur;i++) {
      if(cur%i==0) {
        tmp.push(i);
        factorHelp(cur/i,tmp,res);
        tmp.pop();
      }
    }
  }
};

但是这样做的问题是会加入顺序不同的重复解，因为没有对因子的大小加以限制。
改进：

  1. 每次搜索到因子时，将因子i及cur/i加入到最终解中
  2. 由于cur/i已经加入到解中，以及新的因子需要大于解中最后一个因子；遍历范围为[临时路径的最后一个因子,当前数的开方]，不然会产生重复解
1
2
3
4
5
6
7
8
9
10
11
12
13
var factorHelp = function (cur, tmp, res) {
  var i = tmp.length === 0 ? 2 : tmp[tmp.length - 1];
  for (; i <= cur / i; i++) {
    if (cur % i == 0) {
      tmp.push(i);
      tmp.push(cur / i);
      res.push(tmp.slice(0));
      tmp.pop();
      factorHelp(cur / i, tmp, res);
      tmp.pop();
    }
  }
};

267.Palindrome Permutation II
给定字符串，对字符串进行移动操作，求所有组成非重复回文字符串的组合

该题指定参考Permutations II or Next Permutation，分别是求所有非重复排列组合题及求下一个操作数题。
两种思路

  1. 参考Permutations II，对所有非重复排列进行回溯，若满足回文条件，添加解
  2. 参考Next Permutation，排序字符串，每次求下一个组合，满足回文条件则添加该解，没有用到回溯。

就自己观点，回溯法只是进行了穷举，没有判断的操作，复杂度为O(n!)，第二种方法由于考虑到顺序有判断及交换的行为，复杂度较高。 此处不一定正确！需要大神指点

优化：建立字典判断字符串是否满足可构成回文串条件，若满足则仅用能一半字符串来回溯即可，需要对奇数项字符进行特殊记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
var palinPermutations = function (str) {
  var map = new Array(256).fill(0);
  var res = [];
  for (var i = 0; i < str.length; i++) {
    map[str.charCodeAt(i)]++;
  }
  var odd = 0, halfStr = "", oddChar = "";
  for (i = 0; i < 256; i++) {
    if (map[i] != 0 && map[i] % 2 == 1) {
      odd++;
      oddChar += String.fromCharCode(i);
    }
    if (odd > 1) return res;
    for (var j = 0; j < parseInt(map[i] / 2); j++) {
      halfStr += String.fromCharCode(i);
    }
  }
  console.log("oddChar:", oddChar);
  var used = new Array(str.length).fill(false);
  var tmp = "";
  permutationHelp(halfStr, used, tmp, oddChar, res);
  return res;
};

var permutationHelp = function (str, used, tmp, oddChar, res) {
  if (tmp.length == str.length) {
    res.push(tmp.substr(0) + oddChar + tmp.split('').reverse().join(''));
    return;
  }
  for (var i = 0; i < str.length; i++) {
    if (used[i]) continue;
    if (i > 0 && !used[i - 1] && str[i] == str[i - 1]) continue;
    tmp += str[i];
    used[i] = true;
    permutationHelp(str, used, tmp, oddChar, res);
    used[i] = false;
    tmp = tmp.substr(0, tmp.length - 1);
  }
};

291.Word Pattern II
给定字符串与匹配模式，判断是否匹配
Input: ererdfdf aabb
Output: True

这道题是参考论坛的解决思路：

  1. 建立字典与集，分别存放已用来匹配的[模式：字符串]和[字符串]
  2. 模式从前往后遍历，若在字典当中，匹配对应字符串，失败则返回false，成功则继续往下匹配；不在字典当中，则往字典与集中依次加入i长度的字符串来对应该模式字符，若匹配到模式结尾或者长字符串结尾还是失败，则进行回溯。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    var wordPattern = function (pattern, str) {
      var map = {}, set = {};
      var i = 0, j = 0;
      return matchHelp(pattern, str, i, j, map, set);
    };
    var matchHelp = function (pattern, str, i, j, map, set) {
      console.log("map:", map);
      if (i == pattern.length && j == str.length) return true;
      if (i >= pattern.length || j >= str.length) return false;
      if (map[pattern[i]] !== undefined) {
        var tmpWord = map[pattern[i]];
        if (!str.substr(j).startsWith(tmpWord)) return false;
        return matchHelp(pattern, str, i + 1, j + tmpWord.length, map, set);
      } else {
        for (var k = j; k < str.length; k++) {
          var tmpWord = str.substring(j, k + 1), tmpPtn = pattern[i];
          if (set[tmpWord] !== undefined) continue;
          set[tmpWord] = 1;
          map[tmpPtn] = tmpWord;
          if (matchHelp(pattern, str, i + 1, j + tmpWord.length, map, set)) return true;
          delete map[tmpPtn];
          delete set[tmpWord];
        }
      }
      return false;
    };