java 深度优先搜索（回溯法）

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

package org.iaiai.suanfa;

import java.util.ArrayList;
import java.util.List;

/**
 * 
 * <p>
 * Title: BackTrack.java
 * </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);
    }
  }

}

输出:

[quote]

[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]

[]

[/quote]