java 深度优先搜索（回溯法）
深度优先遍历类似于树的前序遍历。采用的搜索方法的特点是尽可能先对纵深方向进行搜索。这种搜索方法称为深度优先搜索(Depth-First Search)。相应地，用此方法遍历图就很自然地称之为图的深度优先遍历。

package org.iaiai.suanfa;import java.util.ArrayList;import java.util.List;/** *  * <p> * Title: BackTrack.java * </p> * <p> * E-Mail: 176291935@qq.com * </p> * <p> * QQ: 176291935 * </p> * <p> * Http: iaiai.iteye.com * </p> * <p> * Create time: 2011-8-5 * </p> *  * @author 丸子 * @version 0.0.1 */public class BackTrack {public static void main(String[] args) {// 初始化一个集合，放在list里面List<String> list = new ArrayList<String>();list.add("1");list.add("2");list.add("3");list.add("f");List<String> li = new ArrayList<String>();PowerSet(0, list, li);}// 回溯法求幂集public static void PowerSet(int i, List<String> list, List<String> li) {if (i > list.size() - 1) {System.out.println(li);} else {li.add(list.get(i));// 左加PowerSet(i + 1, list, li); // 递归方法li.remove(list.get(i)); // 右去PowerSet(i + 1, list, li);}}}

输出:
引用
[1, 2, 3, 4]
[1, 2, 3]
[1, 2, 4]
[1, 2]
[1, 3, 4]
[1, 3]
[1, 4]
[1]
[2, 3, 4]
[2, 3]
[2, 4]
[2]
[3, 4]
[3]
[4]
[]