子集和数问题——回溯法

                                                           子集和数问题——回溯法

 

 

 

                回溯算法可以用来求最优解，也可以用来搜索某些问题的答案。回溯法又叫做试探法，它是以深度优先遍历的方式找各种符合要求的答案，在查找过程中伴随着一些减枝函数来提高效率。这种算法比较简单，比较出名的问题有8皇后问题。这个子集和数问题也可以用回溯法搞定。。。

              所谓子集和数问题，就是给定你一个数的集合M，再给你一个数num，找出所有属于M且和为num的数的集合。比如M={1,2,3} num=3，则N为{1,2}和{3}。这些都比较简单，还是直接上代码吧。。。

public class SubNum {

	// 初始化化一个数组
	int M[] = {1,2,3,4,5,6,7,8,9};
	int N[] = new int[9];
	//用来标识在某种组合中某个数字是否出现
	boolean [] judge =new boolean [9];
	int num;//给定的num
	int temp;//保存和

	// 初始化化num
	public SubNum(int num) {
		this.num = num;
	}

	// 采用回溯法解决。。
	public void findSub() {
		for (int a = 0; a < M.length; a++) {
			for (int b = a + 1; b < M.length; b++) {
				for(int i=0;i<M.length;i++){//初始化标示数组
					judge [i]=false;
				} 
				temp = M[a];
				judge[a]=true;
				for (int c = b; c < M.length; c++) {
					temp += M[c];
					judge[c]=true;
					if (num == temp) {// 子集找到
						for(int i=0;i<M.length;i++){
							if(judge[i]==true)
								System.out.print(M[i]+"+");
						}
						System.out.print("是一种答案");
						System.out.println();
						temp = temp - M[c];//回溯上一个节点
						judge[c]=false;
					} else if (temp > num) {// 若果大于，则不加这个数，加下一个。
						temp = temp - M[c];
						judge[c]=false;
					} else if (temp < num) {
						// break;// 如果仍小于，继续+。
					}
				}
			}
		}
	}

	public void testlast(){
		if (M[M.length - 1] == num)//测试最后一位是否满足条件。。。
			System.out.println(M[M.length-1] + "是一种答案");
	}
	public static void main(String[] agrs) {
		SubNum sn = new SubNum(12);
		sn.findSub();
                sn.testlast();
        }
}

 测试结果为：

1+5+6+是一种答案
3+4+5+是一种答案
3+9+是一种答案
4+8+是一种答案
5+7+是一种答案

                    上面的代码有不完善的地方，我减去的旁枝较少，效率还不是很高，不过能基本体现回溯法。。。总之，理解了回溯法深度优先遍历且尽量剪去不必要枝叶的思想即可。。。