LeetCode306——累加数（回溯算法）

LeetCode306——累加数（回溯算法）

首先要知道回溯算法的一般套路为：

//添加路径
track.add(路径);
//进入下一个决策树
backTrack();
//撤销选择
track.remove(路径);

它是一种暴力穷举的算法，在此基础上，进行剪支以降低回溯的次数。

下面来看一道算法题。
LeetCode306

判断一个字符串是否为累加数，意思很明确，但是难点在于如何找到第一个数和第二个数，只要找到这两个数，一直加下去看是不是等于后面那个数就完了，只要有一次不相等，就需要重新确定第一个数和第二个数。如果试过了所有的情况都不行，那么就不是累加数。

因此，容易想到的方法是穷举第一个数和第二个数，在这里可以利用三个性质进行剪支：

• 第一个数的长度不会超多总长度的一半
• 第三个数的长度要大于第一个数和第二个数长度的最大值
• 第一个数和第二个数不能以0为开头，但是单独为0是可以的

接下来上代码：

public boolean isAdditiveNumber(String num) {
	String str1 = "", str2 = "", str3 = "";
	for(int i = 0; i < num.length() / 2 + 1; i++){
        for(int j = i+1; j < nums.length(); j++){
        	str1 = num.substring(0,i);
        	str2 = num.substring(i,j);
        	str3 = num.substring(j);
        	//剪支
        	if(str1.charAt(0) == '0' && str1.length() != 1) continue;
        	if(str2.charAt(0) == '0' && str2.length() > 1) continue;
        	if(str3.length() < Math.max(str1.length(),str2.length())) break; 
        	//判断
        	if(backTrack(str1,str2,str3)) return true;
        }
    }
    //所有情况都不满足
    return false;
}

public boolean backTrack(String str1, String str2, String str3){
	//这里要用long，否则会溢出
	long sum = Long.parseLong(str1) + Long.parseLong(str2);
	String s = String.valueOf(sum);
	if(str3.startsWith(s)){//以str1+str2为开头，说明有戏，需要一步一步判断后面的
		str1 = str2;
		str2 = str3.substring(0,s.length());
		str3 = str3.substring(s.length());
		if(str3.length() == 0) return true;//表示已经判断到结尾了
		//否则就继续下一轮判断
		return backTrack(str1,str2,str3);
	}else{ //只要有一个不满足，立马返回false,进行下一次穷举
	    return false;
	}
}