1. // 回溯算法伪代码
    2. function backtracking(参数) {
    3.  if (终⽌条件) {
    4.  存放结果;
    5.  return;
    6.  }
    7.  for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩）) {
    8.  处理节点;
    9.  backtracking(路径，选择列表); // 递归
    10.  回溯，撤销处理结果
    11.  }
    12. }
    14. // 回溯求子集
    16. function backtracking(nums, startIndex, path, result) {
    17.     result.push(path); // 收集⼦集，要放在终⽌添加的上⾯，否则会漏掉⾃⼰
    18.     if (startIndex >= nums.length) { // 终⽌条件可以不加
    19.         return;
    20.     }
    21.     for (let i = startIndex; i < nums.length; i++) {
    22.         path.push(nums[i]);
    23.         backtracking(nums, i + 1, [...path], result);
    24.         path.pop();
    25.     }
    26. }
    28. function subsets(nums) {
    29.     result = [];
    30.     path = [];
    31.     backtracking(nums, 0, path, result);
    32.     return result;
    33. }
    36. // 复原IP地址
    37. 给定⼀个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
    38. 有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间⽤
    39. '.' 分隔。
    40. 例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和
    41. "192.168@1.1" 是 ⽆效的 IP 地址。
    43. // 判断字符串s在左闭⼜闭区间[start, end]所组成的数字是否合法
    44. function isValid(s, start, end) {
    45.     if (start > end) {
    46.         return false;
    47.     }
    48.     if (s[start] == '0' && start != end) { // 0开头的数字不合法
    49.         return false;
    50.     }
    51.     let num = 0;
    52.     for (let i = start; i <= end; i++) {
    53.         if (s[i] > '9' || s[i] < '0') { // 遇到⾮数字字符不合法
    54.             return false;
    55.         }
    56.         num = num * 10 + (s[i] - '0');
    57.         if (num > 255) { // 如果⼤于255了不合法
    58.             return false;
    59.         }
    60.     }
    61.     return true;
    62. }
    64. function backtracking(s, startIndex, pointNum,result) {
    65.     if (pointNum == 3) { // 逗点数量为3时，分隔结束
    66.         // 判断第四段⼦字符串是否合法，如果合法就放进result中
    67.         if (isValid(s, startIndex, s.length - 1)) {
    68.             result.push(s);
    69.         }
    70.         return;
    71.     }
    72.     for (let i = startIndex; i < s.length; i++) {
    73.         if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的⼦串是否合法
    74.             s = s.slice(0, i + 1) + '.' + s.slice(i + 1); // 在i的后⾯插⼊⼀个逗点
    75.             pointNum++;
    76.             backtracking(s, i + 2, pointNum,result); // 插⼊逗点之后下⼀个⼦串的起始位置为i + 2
    77.             pointNum--; // 回溯
    78.             s = s.slice(0, i + 1) + s.slice(i + 2); // 回溯删掉逗点
    79.         } else break; // 不合法，直接结束本层循环
    80.     }
    81. }
    83. function restoreIpAddresses(s) {
    84.     let result = [];
    85.     if (s.length > 12) return result; // 算是剪枝了
    86.     backtracking(s, 0, 0,result);
    87.     return result;
    88. }
    91. console.log(restoreIpAddresses("25525511135"))
    99. class Solution {
    100. private:
    101.  vector<vector<int>> result;
    102.  vector<int> path;
    103.  void backtracking(vector<int>& candidates, int target, int sum, int
    104. startIndex, vector<bool>& used) {
    105.  if (sum == target) {
    106.  result.push_back(path);
    107.  return;
    108.  }
    109.  for (int i = startIndex; i < candidates.size() && sum + candidates[i]
    110. <= target; i++) {
    111.  // used[i - 1] == true，说明同⼀树⽀candidates[i - 1]使⽤过
    112.  // used[i - 1] == false，说明同⼀树层candidates[i - 1]使⽤过
    113.  // 要对同⼀树层使⽤过的元素进⾏跳过
    114.  if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] ==
    115. false) {
    116.  continue;
    117.  }
    118.  sum += candidates[i];
    119.  path.push_back(candidates[i]);
    120.  used[i] = true;
    121.  backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和
    122. 的区别1，这⾥是i+1，每个数字在每个组合中只能使⽤⼀次
    123.  used[i] = false;
    124.  sum -= candidates[i];
    125.  path.pop_back();
    126.  }