10.24 暴力dfs。。。 时间 O(3^(N-1)*N) : 3^(N-1) dfs 每种情况 N 时间计算+判断

gistfile1.txt

/*
  Level 1: 序列123...N，N介于3和9之间，在其中加入+、-或者空格，使其和为0。如123456  1-2 3-4 5+6 7 等价于1-23-45+67=0。请问，如何获得所有组合？ 
*/

import java.util.ArrayList;

/* we use :
0 : space
1 : +
2 : -
*/
public class FindInsertion {
	public ArrayList<ArrayList<Integer>> findInsertion(int n){
		ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
		findInsertion(res,n-1,new ArrayList<Integer>());
		return res;
	}

	public void findInsertion(ArrayList<ArrayList<Integer>> res, int slot, ArrayList<Integer> curPath){
		


		if (curPath.size()>=slot){
			if (calc(curPath)==0){
				res.add(curPath);
			}
			
			return;
		} 
		ArrayList<Integer> newPath0 = new  ArrayList<Integer>(curPath); 
		newPath0.add(0);
		findInsertion(res,slot,newPath0);
		
		ArrayList<Integer> newPath1 = new  ArrayList<Integer>(curPath);
		newPath1.add(1);
		findInsertion(res,slot,newPath1);

		ArrayList<Integer> newPath2 = new  ArrayList<Integer>(curPath);
		newPath2.add(2);
		findInsertion(res,slot,newPath2);
	}

	public int calc(ArrayList<Integer> path){
		int sum=0;
		// add from end to front
		int i=path.size()+1;
		// current number
		int cur=i; 
		for (int j=path.size()-1;j>=0;j--){
			if (path.get(j)==0){
				i--;
				cur += i*10;
			} else if(path.get(j)==1) {
				sum += cur;
				i--;
				cur = i;
			} else {
			// path[j] == 2
				sum -= cur;
				i--;
				cur = i;
			}
		}
		// handle the first num  1XX, always plus
		sum += cur;
		return sum;
	}
	
	public static void main(String[] args){
		FindInsertion instance = new FindInsertion();
		
		ArrayList<ArrayList<Integer>> res = instance.findInsertion(7);
		System.out.println(res);
	}
}