前言
记录 LeetCode 刷题时遇到的回溯相关题目，第二篇。
93. 复原 IP 地址
回溯函数 backTrack(int index,int offset) 表示从原字符串中 offset 位置开始 (包括 offset) 选数来凑出 IP 地址中第 index 个数 (index 从 0 开始)
class Solution {
int[] numIndex = new int[4]; //存放那四个数
private char[] chars;
int sLength;
List<String> res = new LinkedList<>();
public void backTrack(int index,int offset){
if(index == 4){ // 边界1，当index增长到4，说明已经凑出了四个数，但是 offset 不等于字符串长度的话，说明后面还有数字没有被选，所以回溯
if(offset == sLength) res.add(numIndex[0] + "." + numIndex[1] + "." + numIndex[2] + "." + numIndex[3]);
return;
}
if(offset >= sLength) return; // 边界2，offset超出字符串范围
if(chars[offset] == '0'){ // 剪枝1，如果第一位为 0 ，那么这一个数只能取 0
numIndex[index] = 0;
backTrack(index + 1,offset + 1);
return;
}
int num = 0;
//从offset 开始一个数一个数选
for(int i = offset;i < sLength && i < offset + 3;i++){
num = num * 10 + chars[i] - '0';
if(num > 255) break;
numIndex[index] = num;
backTrack(index + 1,i + 1);
}
}
public List<String> restoreIpAddresses(String s) {
sLength = s.length();
if(sLength < 4 || sLength > 12) return res; // 剪枝2，每个数最多只能为三位，所以整个串最多12位
chars = s.toCharArray();
backTrack(0,0);
return res;
}
}
面试题 08.08. 有重复字符串的排列组合
参考题解
对于重复的字母，在同一位置不能出现多次，例如 “qqe”，在选择 ‘e’ 以及第一个 ‘q’ 后，后续不能选择 ‘e’ 以及第二个 ‘q’，
class Solution {
List<String> list = new ArrayList<>();
public String[] permutation(String S) {
char[] c = S.toCharArray();
boolean[] used = new boolean[c.length];
StringBuilder sb = new StringBuilder();
backTrack(used,c,sb);
String[] res = list.toArray(new String[0]);
return res;
}
public void backTrack(int[] used , char[] c, StringBuilder sb){
if (sb.length() == c.length){
list.add(sb.toString());
return;
}
for (int i = 0; i < c.length; i++) {
if (!used[i]){
char cur = c[i];
boolean valid = true;
for (int j = 0; j < i; j++) {
if (!used[j] && c[j] == cur){
//因为在分支选取字母是从左到右选的，所以在cur左边的字母如果used值为false，
//说明这个字母在当前位置已经使用过了，同一个字母在同一位置不应该使用两次
valid = false;
}
}
if (!valid) continue;
sb.append(c[i]);
used[i] = true;
backTrack(used, c, sb);
sb.deleteCharAt(sb.length()-1);
used[i] = false;
}
}
}
}
77. 组合
定义回溯函数 backTrack(int i,int count)，表示从 i 开始 (包括 i) 往后的数中选取出所有可行的组合，当前已选取了 count 个。那么为了得到问题的解，我们只需调用 backTrack(1,0) 即可
对于 backTrack 函数，如果 count 值为 k，说明当前选出的组合 cur 的数目已经达到 k 了，直接把 cur 放入 res 中；如果 i 大于 n，说明待选数已经超出范围了，进行剪枝；否则就从 i 开始直到 n 进行选数
class Solution {
public List<List<Integer>> res;
public List<Integer> cur;
public int n;
public int k;
public List<List<Integer>> combine(int n, int k) {
res = new ArrayList<>();
cur = new ArrayList<>();
this.n = n;
this.k = k;
backTrack(1,0);
return res;
}
public void backTrack(int i,int count){
if(count == k){
res.add(new ArrayList<>(cur));
return;
}
if(i > n) return;
for(int j = i;j <= n;j++){
cur.add(j);
backTrack(j + 1,count + 1);
cur.remove(cur.size() - 1); //回退
}
}
}
变形
如果给定的 n 个数不是 [1,n] 的范围，而是任意的 n 个数，且会有重复，怎么处理？
最简单的方式就是基于上面回溯的做法，把 count == k 时得到的 cur 添加到一个 Set 中，然后每次在把 cur 添加到 res 前看看 Set 中是否已存在 cur，存在的话就不添加到 res 中
679. 24 点游戏
4 个数进行 24 点游戏，我们可以先选出两个数进行运算，这样四个数就变为 3 个数；然后同理，再选出两个数进行运算，剩下两个数，再对这两个数进行运算，得到最终的结果，判断是否为 24 即可。因此很明显是一个递归的过程，对四个数选出两个数进行计算后对三个数进行递归，然后再对两个数递归…
由于对两个数运算有 6 种方式 (减跟除中两个运算数交换顺序)，因此需要进行回溯从而覆盖 6 种运算方式
需要注意的：
- 除法运算是实数运算，所以计算结果可能是实数，所以每个数要转化为 double 处理，才不会出现 0 的运算结果
- 同样由于是实数运算，最后的运算结果不一定刚好等于 24，而是一个近似于 24 的实数，所以判断最后的运算结果是否为 24 需要通过与 24 做差判断差值是否足够小来判断
class Solution {
public boolean judgePoint24(int[] cards) {
//知道list中最多只会有4个数，直接设置好大小为4，避免扩容
List<Double> list = new ArrayList<>(4);
for(int i : cards){
list.add((double)i);
}
return backTrack(list);
}
public boolean backTrack(List<Double> list){
if(list.size() == 1){
return Math.abs(list.get(0) - 24) <= 1e-6;
}
for(int i = 0;i < list.size() - 1;i++){
for(int j = i + 1;j < list.size();j++){
boolean flag = false;
List<Double> tmp = new ArrayList(list);
//remove后list中i之后的数据会前移，如果先remove掉较小的坐标i的话，j对应的数就发生变化了；所以要先remove掉排在后边的j，这样i对应的数就不会变化
double b = tmp.remove(j);
double a = tmp.remove(i);
tmp.add(a + b);
flag |= backTrack(tmp);
tmp.set(tmp.size() - 1,a - b);
flag |= backTrack(tmp);
tmp.set(tmp.size() - 1,b - a);
flag |= backTrack(tmp);
tmp.set(tmp.size() - 1,a * b);
flag |= backTrack(tmp);
tmp.set(tmp.size() - 1,a / b);
flag |= backTrack(tmp);
tmp.set(tmp.size() - 1,b / a);
flag |= backTrack(tmp);
if(flag) return true;
}
}
return false;
}
}
17. 电话号码的字母组合
每个数字有对应的几个字母，我们可以先定义一个数组存放每个数字对应的所有字母，然后对原字符串进行回溯，对每一个数字选取一个对应的字母进行替换，接着继续回溯后面的数字。回溯结束后回退，选取第二个字母进行替换，再继续回溯后面的数字，直到选取完所有对应的字母
class Solution {
List<String> res;
StringBuilder sb;
char[][] numToChars = new char[][]{
{'a','b','c'},
{'d','e','f'},
{'g','h','i'},
{'j','k','l'},
{'m','n','o'},
{'p','q','r','s'},
{'t','u','v'},
{'w','x','y','z'}
};
public List<String> letterCombinations(String digits) {
if(digits.isEmpty()){
return new ArrayList<>();
}
char[] cs = digits.toCharArray();
res = new ArrayList<>();
sb = new StringBuilder();
backTrack(cs,0);
return res;
}
public void backTrack(char[] cs,int idx){
if(idx == cs.length){
res.add(sb.toString());
return;
}
char[] toChars = numToChars[cs[idx] - '2'];
for(char c : toChars){
sb.append(c);
backTrack(cs,idx + 1);
sb.deleteCharAt(sb.length() - 1);
}
}
}
