求助关于排列组合的递归问题，树的问题，算法求知道

Question

递归排列组合树

Answer 1

    public static void main(String[] args) {
        p(7, "");
    }    public static void p(int i, String pre) {
        if (i == 0) {
            System.out.println(pre);
        } else {
            for (String s : new String[]{"A", "T", "C", "G"}) {
                p(i - 1, pre + s);
            }
        }
    }

Answer 2

static List<Character> candidates = new ArrayList<Character>();
public static void main(String[] args) {
candidates.add( 'A' );
candidates.add( 'T' );
candidates.add( 'C' );
candidates.add( 'G' );
int k = 2;
ArrayList<ArrayList<Character>> result = new ArrayList<ArrayList<Character>>();
ArrayList<Character> curList = new ArrayList<Character>();
permutation( k, 1, curList, result );
for( ArrayList<Character> res : result )
System.out.println( res );
}
public static void permutation( int k, int l, ArrayList<Character> curList, ArrayList<ArrayList<Character>> result ) {
if( l > k ) {
result.add( (ArrayList<Character>)curList.clone() );
return;
}
for( int i= 0; i < 4; i++  ) {
curList.add( candidates.get( i ) );
permutation( k, l+1, curList, result );
curList.remove( curList.size() - 1 );
}
}

Answer 3

月经题了，属于典型的解空间遍历问题，无非是两种解决方案:DFS和BFS
import java.util.LinkedList;
import java.util.Queue;
public class Select {
    
/**先序遍历法:深度搜索解空间  递归
 * @param array  数组
 * @param k      最多k层
 * @param level  当前层次
 * @param parent 父节点串
 */
public static void dfs(String[] array,int k,int level,String parent){
    if(level==k){
        count++;
        //System.out.println(parent);
    }else{
        for(int i=0;i<array.length;i++){
            dfs(array, k, level+1, parent+array[i]);
        }
        
    }
}
/**层序遍历法:广度搜索解空间  非递归
 * @param array
 * @param k
 */
public static void bfs(String[] array,int k){
    Node root=new Node(0, "");
    Queue<Node> queue=new LinkedList<Node>();
    queue.offer(root);
    Node p=null;
    Node child=null;
    while(queue.peek().level!=k){
        p=queue.poll();
        for(int i=0;i<array.length;i++){
            child=new Node(p.level+1, p.str+array[i]);
            queue.offer(child);
        }
    }
    System.out.println("BFS:"+(count==queue.size()));
    while(!queue.isEmpty()){
        p=queue.poll();
        //System.out.println(p.str);
    }
}
/**用来验证是不是 4的k次方种可能性  */
public static int count=0;
public static void main(String[] args) {
    String[] array={"A","T","C","G"};
    int k=7;
    dfs(array, k, 0, "");
    System.out.println("DFS:"+(count==Math.pow(array.length, 7)));
    bfs(array, k);
}
}
/**
解空间的辅助节点
 */
class Node{
    /** 层数 */
    int level;
    /** 串 */
    String str;
    public Node(int level, String str) {
        super();
        this.level = level;
        this.str = str;
    }   
}结果:
DFS:true
BFS:true