回溯算法是什么

public class Queen
{
	// 方案数
	public static int num = 0;
	// 皇后数
	public static final int MAXQUEEN = 8;
	// 定义数组，表示MAXQUEEN列棋子中皇后摆放位置
	public static int[] cols = new int[MAXQUEEN];

	public void getCount(int n)
	{
		boolean[] rows = new boolean[MAXQUEEN];
		for (int m = 0; m < n; m++)
		{
			// rows 为true 表名不可以放，垂直上面不可放
			rows[cols[m]] = true;

			int d = n - m;
			// y=x 这条线 往前判断
			if (cols[m] - d >= 0)
			{
				rows[cols[m] - d] = true;
			}
			// y=-x这条线 往右边判断
			if (cols[m] + d <= (MAXQUEEN - 1))
			{
				rows[cols[m] + d] = true;
			}
		}

		for (int i = 0; i < MAXQUEEN; i++)
		{
			if (rows[i])
			{
				//如果这一行中的 某个列位置 不可放置则继续看下个位置。
				continue;
			}
			cols[n] = i;
			//如果下面还没填充完毕 则仍需合法位置
			if (n < MAXQUEEN - 1)
			{
				getCount(n + 1);
			} else
			{
				// 找到完整的一套方案
				num++;
				printQueen();
			}
		}
	}

	private void printQueen()
	{
		System.out.println("第">

package practice;
 
/**
 * 给定n种物品和一背包。物品i的重量是wi，其价值为pi，背包的容量为C。 问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
 * 
 * @author fulisha
 *
 */
public class _05 {
 
	static int BestValue = 0; // 最优值；当前的最大价值，初始化为0
	static int[] BestX; // 最优解；BestX[i]=1代表物品i放入背包，0代表不放入
	//
	static int CurWeight = 0; // 当前放入背包的物品总重量
	static int CurValue = 0; // 当前放入背包的物品总价值
	static int N = 3;// 物品数量
	static int C = 16;// 物品的总容量
	static int W[] = { 10, 8, 5 }; // 每个物品的重量
	static int v[] = { 5, 4, 1 };// 每个物品的价值
	static int x[] = { 0, 0, 0 };// x[i]=1代表物品i放入背包，0代表不放入
 
	public static int backtrack(int t) {
		// 如果是子节点 当前价值和最佳价值做判断 保存最佳价值
		if (t > N - 1) {
			if (CurValue > BestValue) {
				BestValue = CurValue;
			}
			return BestValue;
		}
		// 如果不是子节点 对子节点进行遍历
		else {
			// 就两种情况 取或不取 用0/1表示
			for (int i = 0; i <= 1; i++) {
				x[t] = i;
				if (i == 0) {
					// 如果是不取 就不需要进行判断 直接到下一个节点
					backtrack(t + 1);
				} else
				// 放入背包就进行约束条件 判断放入背包的东西是否合法
				{
					if (CurWeight + W[t] <= C) {
						CurWeight += W[t];
						CurValue += v[t];
						// 当东西装进入背包后你可以进行对下个商品的判断了
						backtrack(t + 1);
						//能执行以下两个语句就说明你回溯到了上一个节点 
                       // 所以你就需要恢复现场 把你刚刚拿的东西退出来 
                       // 我们要冲上一个节点又要重新来遍历 如果不减你就会多加一遍 
						CurWeight -= W[t];
						CurValue -= v[t];
					}
				}
			}
		}
		return BestValue;
	}
 
	public static void main(String[] args) {
		backtrack(0);
		System.out.println(BestValue);
		for (int i = 0; i < 3; i++) {
			// System.out.println(BestX[i]);
		}
	}
 
}

public class TestMaze
{
	// 定义一个二维数组做迷宫
	private int[][] maze = null;
	//表示此迷宫一共有几种走法
	private int count = 0;
	// 迷宫的开始位置和结束位置的坐标
	private static int startI, startJ, endI, endJ;

	private void setStart(int i, int j)
	{
		startI = i;
		startJ = j;
	}
	private void setEnd(int i, int j)
	{
		endI = i;
		endJ = j;
	}
	private void show()
	{
		System.out.println("第">{2, 2, 2, 2, 2, 2, 2, 2},
						{2, 0, 0, 0, 0, 2, 2, 2},
						{2, 0, 2, 0, 0, 0, 2, 2},
						{2, 0, 0, 2, 0, 2, 0, 2},
						{2, 0, 0, 2, 0, 2, 2, 0},
						{2, 0, 2, 0, 0, 0, 0, 2},
						{2, 0, 0, 0, 0, 2, 0, 2},
						{2, 2, 2, 2, 2, 2, 2, 2}};
		myMaze.maze = maze;
		myMaze.setStart(1, 1);
		myMaze.setEnd(6, 6);
		myMaze.play(1, 1);
	}
}

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

	/**
	 * list：用来存储符合要求的括号组合。
	 * 局部变量temp:表示当前函数的括号组成样式。
	 * 计数器x：判断递归次数，限制其底界。
	 * 总的形成括号对数n。
	 * */
	public List<String> generateParenthesis(int n)
	{
		List<String> list = new ArrayList<>();
		add_list(list, "(", 1, n * 2);
		return list;
	}

	//书写递归函数
	public void add_list(List<String> list, String temp, int x, int n)
	{
		x++;
		if (x <= n)
		{
			// 尽可能罗列 括号的存在
			add_list(list, temp + "(", x, n);
			add_list(list, temp + ")", x, n);

		}
		if (x > n)
		{
			//在这里写判断条件是否负荷有效的括号组合
			char[] k = temp.toCharArray();
			//计数器
			int timer = 0;
			for (int i = 0; i < k.length; i++)
			{
                //无论何时 ( 个数 >= ）个数
				if (timer < 0 || timer > n / 2)
				{
					return;
				} else
				{
					if (k[i] == '(')
					{
						timer++;
					} else
					{
						timer--;
					}
				}
			}
			if (timer == 0)
				list.add(temp);
		}

	}
====

import java.util.ArrayList;
import java.util.List;
 
 
public class generateParenthesis {
	//参数有n对的{}()[],
	public static List<String> generater(int n) {
		List<String> result=new ArrayList<String>();
		generaterOneByOne("",result,n,n);
		return result;
	}
	/**
	 * left:左边的括号就n个
	 * right:右边的括号有n个
	 * 思想：
	 *   必须先放左边的括号，以递归的方式，然后直到左边的括的数目小于0时，以及右边的括号为0时，截止并放到结果中
	 *   右边的括号要后放：也就是right>left，保证右括号大于左边括号的数目
	 * @param substring
	 * @param result
	 * @param left
	 * @param right
	 */
	private static void generaterOneByOne(String substring, List<String> result, int left, int right) {
		if (left==0&&right==0) {
			result.add(substring);
			return;
		}
		if (left>0) {
			generaterOneByOne(substring+"(", result, left-1, right);
		}
		if (right>left) {
			generaterOneByOne(substring+')', result, left, right-1);
		}		
	}
 
}