【算法】-回溯

回溯

回溯法可以看作蛮力法的升级版,它在解决问题时的每一步都尝试所有可能的选项,最终找出所有可行的解决方案。回溯法非常适合解决由多个步骤组成的问题,并且每个步骤都有多个选项。在某一步选择了其中一个选项之后,就进入下一步,然后会面临新的选项。就这样重复选择,直至到达最终的状态。

由于回溯法是在所有选项形成的树上进行深度优先遍历,如果解决问题的步骤较多或每个步骤都面临多个选项,那么遍历整棵树将需要较多的时间。如果明确知道某些子树没有必要遍历,那么在遍历的时候应该避开这些子树以优化效率。通常将使用回溯法时避免遍历不必要的子树的方法称为剪枝。

集合的组合、排列

从一个包含 m 个元素的集合中挑选出 n 个元素(0≤n≤m)形成一个子集。一个子集又可以称为一个组合。如果两个子集(组合)的元素完全相同只是顺序不同,那么它们可以看作同一个子集(组合)。
从一个包含 m 个元素的集合中挑选出 n 个元素(0≤n≤m)并按照某种顺序形成一个排列。m 等于 n 的排列又称为全排列。如果两个排列的元素完全相同只是顺序不同,那么它们就是两个不同的排列。也就是说,排列与元素的顺序相关,这一点与组合不同。

  1. 所有子集
输入一个不含重复数字的数据集合,请找出它的所有子集。例如,数据集合[1,2]有 4 个子集,分别是[]、[1]、[2]和[1,2]。
var helper = function (nums, index, subset, result) {
  if (index == nums.length) {
    result.push(subset.slice()); // 子集要深拷贝
  } else if (index < nums.length) {
    helper(nums, index + 1, subset, result);
    subset.push(nums[index]);
    helper(nums, index + 1, subset, result);
    subset.pop();
  }
};

var subsets = function (nums) {
  let result = [];
  if (nums.length == 0) return result;
  helper(nums, 0, [], result);
  return result;
};
var subsets = function (nums) {
  const t = [];
  const ans = [];
  const n = nums.length;
  const dfs = (cur) => {
    if (cur === nums.length) {
      ans.push(t.slice());
      return;
    }
    t.push(nums[cur]);
    dfs(cur + 1, nums);
    t.pop(t.length - 1);
    dfs(cur + 1, nums);
  };
  dfs(0, nums);
  return ans;
};
  1. 含有 k 个元素的组合
给定两个整数 n 和 k,返回 1 ... n 中所有可能的 k 个数的组合。
var helper = function (nums, index, subset, result, k) {
  if (index == nums.length && subset.length == k) {
    result.push(subset.slice()); // 子集要深拷贝
  } else if (index < nums.length) {
    helper(nums, index + 1, subset, result, k);
    subset.push(nums[index]);
    helper(nums, index + 1, subset, result, k);
    subset.pop();
  }
};

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function (n, k) {
  let nums = new Array(n);
  for (let i = 0; i < n; i++) {
    nums[i] = i + 1;
  }
  let result = [];
  if (nums.length == 0) return result;

  helper(nums, 0, [], result, k);
  return result;
};
  1. 允许重复选择元素的组合
给定一个没有重复数字的正整数集合,请找出所有元素之和等于某个给定值的所有组合。同一个数字可以在组合中出现任意次。例如,输入整数集合[2,3,5],元素之和等于 8 的组合有 3 个,分别是[2,2,2,2]、[2,3,3]和[3,5]。
var helper = function (nums, index, subset, result, target) {
  if (target == 0) {
    result.push(subset.slice());
  } else if (target > 0 && index < nums.length) {
    helper(nums, index + 1, subset, result, target);
    subset.push(nums[index]);
    helper(nums, index, subset, result, target - nums[index]);
    subset.pop();
  }
};
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
  let result = [];
  if (candidates.length == 0) return result;
  helper(candidates, 0, [], result, target);
  return result;
};
  1. 包含重复元素集合的组合
给定一个可能包含重复数字的整数集合,请找出所有元素之和等于某个给定值的所有组合。输出中不得包含重复的组合。例如,输入整数集合[2,2,2,4,3,3],元素之和等于 8 的组合有 2 个,分别是[2,2,4]和[2,3,3]。
var getNext = function (nums, index) {
  let next = index;
  while (next < nums.length && nums[next] == nums[index]) {
    next++;
  }
  return next;
};

var helper = function (nums, index, subset, result, target) {
  if (target == 0) {
    result.push(subset.slice());
  } else if (target > 0 && index < nums.length) {
    helper(nums, getNext(nums, index), subset, result, target);
    subset.push(nums[index]);
    helper(nums, index + 1, subset, result, target - nums[index]);
    subset.pop();
  }
};

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function (candidates, target) {
  let result = [];
  if (candidates.length == 0) return result;
  candidates.sort((a, b) => a - b);

  helper(candidates, 0, [], result, target);
  return result;
};
  1. 没有重复元素集合的全排列
给定一个没有重复数字的集合,请找出它的所有全排列。例如,集合[1,2,3]有 6 个全排列,分别是[1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]和[3,2,1]。

没想明白

var swap = function (nums, i, j) {
  if (i !== j) {
    let temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
};

var helper = function (nums, i, result) {
  if (i == nums.length) {
    result.push(nums.slice());
  } else {
    for (let j = i; j < nums.length; j++) {
      swap(nums, i, j);
      helper(nums, i + 1, result);
      swap(nums, i, j);
    }
  }
};

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function (nums) {
  const result = [];
  helper(nums, 0, result);
  return result;
};
  1. 含有重复元素集合的全排列
给定一个可包含重复数字的整数集合 nums ,按任意顺序 返回它所有不重复的全排列。
var swap = function (nums, i, j) {
  if (i !== j) {
    let temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
  }
};

var helper = function (nums, i, result) {
  if (i == nums.length) {
    result.push(nums.slice());
  } else {
    let map = new Map();
    for (let j = i; j < nums.length; j++) {
      if (!map.get(nums[j])) {
        map.set(nums[j], true);
        swap(nums, i, j);
        helper(nums, i + 1, result);
        swap(nums, i, j);
      }
    }
  }
};

var permute = function (nums) {
  const result = [];
  helper(nums, 0, result);
  return result;
};

使用回溯解决其他类型问题

除了可以解决与集合排列、组合相关的问题,回溯法还能解决很多算法面试题。如果解决一个问题需要若干步骤,并且每一步都面临若干选项,当在某一步做了某个选择之后前往下一步仍然面临若干选项,那么可以考虑尝试用回溯法解决。通常,回溯法可以用递归的代码实现。

适用回溯法的问题的一个特征是问题可能有很多个解,并且题目要求列出所有的解。
如果题目只是要求计算解的数目,或者只需要求一个最优解(通常是最大值或最小值),那么可能需要运用动态规划。

  1. 生成匹配的括号
输入一个正整数 n,请输出所有包含 n 个左括号和 n 个右括号的组合,要求每个组合的左括号和右括号匹配。例如,当 n 等于 2 时,有两个符合条件的括号组合,分别是"(())"和"()()"
var helper = function (left, right, parenthesis, result) {
  if (left === 0 && right === 0) {
    result.push(parenthesis);
    return;
  }
  if (left > 0) {
    helper(left - 1, n, parenthesis + "(", result);
  }

  if (left < right) {
    helper(left, n - 1, parenthesis + ")", result);
  }
};

var generateParenthesis = function (n) {
  let result = [];
  helper(n, n, "", result);
  return result;
};
  1. 分割回文子字符串
输入一个字符串,要求将它分割成若干子字符串,使每个子字符串都是回文。请列出所有可能的分割方法。例如,输入"google",将输出 3 种符合条件的分割方法,分别是["g","o","o","g","l","e"]、["g","oo","g","l","e"]和["goog","l","e"]。
var isPalindrome = function (str, start, end) {
  while (start < end) {
    if (str.chatAt(start++) !== str.charAt(end--)) {
      return false;
    }
  }
  return true;
};

var helper = function (str, start, substrings, result) {
  if (start === str.length) {
    result.push(substrings.slice());
  } else {
    for (let i = start; i < str.length; i++) {
      if (isPalindrome(str, start, i)) {
        substrings.push(str.substring(start, i + 1));
        helper(str, i + 1, substrings, result);
        substrings.pop();
      }
    }
  }
};

var partition = function (s) {
  let result = [];
  helper(s, 0, [], result);
  return result;
};
  1. 恢复 IP 地址
输入一个只包含数字的字符串,请列出所有可能恢复出来的 IP 地址。例如,输入字符串"10203040",可能恢复出 3 个 IP 地址,分别为"10.20.30.40"、"102.0.30.40"和"10.203.0.40"。
var isValidSeg = function(seg) {
    return  Number(seg) <= 255 && (seg == "0" || seg.charAt(0) != '0')
}
var helper = function (s, i, segI, seg, ip, result) {
  if (i == s.length && segI == 3 && isValidSeg(seg)) {
    result.push(ip + seg);
  } else if (i < s.length && segI <= 3) {
    let ch = s.charAt(i)
    if (isValidSeg(seg + ch)) {
        helper(s, i+1, segI, seg + ch, ip, result)
    } 
    if(seg.length > 0 && segI < 3) {
        helper(s, i+1, segI + 1, "" + ch, ip + seg + ".", result)
    }
  }
};
var restoreIpAddresses = function (s) {
  let result = [];
  helper(s, 0, 0, "", "", result);
  return result;
};

总结

本章介绍了用回溯法解决各类典型面试题。如果解决一个问题需要若干步骤,并且在每一步都面临若干选项,那么可以尝试用回溯法解决这个问题。适用回溯法的问题的一个特点是解决这个问题存在多个解,而题目往往要求列出所有的解。

你可能感兴趣的