Java 递归、DFS、回溯

大家好，又见面了，我是你们的朋友全栈君。

DFS/回溯算法

如果某问题的解可以由多个步骤得到，而每个步骤都有若干种选择（这些候选方案集可能会依赖之前做出的选择），且可以用递归枚举法实现，则它的工作方式可以用解答树来描述。

全排列问题

输出数字1~N所能组成的所有全排列

public class A { 
   
    /** * 全排列 * * @param args */

    static Vector<Integer> vector = new Vector<>();

    static int N = 0;

    static boolean[] isUsed = new boolean[100];

    public static void main(String[] args) { 
   

        N = 3;
        dfs(0);
    }

    static void dfs(int n) { 
   
        if (n >= N) { 
   
            for (Integer integer : vector) { 
   
                System.out.print(integer);
            }
            System.out.println();
            return;
        }
        for (int i = 1; i <= N; i++) { 
   
            if (isUsed[i]) { 
   
                continue;
            }
            vector.add(i);
            isUsed[i] = true;
            dfs(n + 1);
            Integer integer = vector.lastElement();
            vector.remove(integer);
            isUsed[i] = false;
        }

    }

}

素数环问题

将1到n这n个整数围成一个圆环，若其中任意2个相邻的数字相加，结果均为素数，那么这个环就成为素数环。

例如数字1-6所组成的一个素数环，用数组表示是[1, 4, 3, 2, 5, 6]（第一位固定为1）

图一：

图二、

public class B { 

static int N = 6;
static Vector<Integer> vector = new Vector<>();
static boolean[] isUsed = new boolean[100];
/** * 1 - n 之间的 * 素数环 * * @param args */
public static void main(String[] args) { 

System.out.println(8 & 1);
vector.add(1);
dfs(1);
}
static void dfs(int n) { 

// 打印结果
if (n >= N) { 

int temp = vector.firstElement() + vector.lastElement();
if (isPri(temp) == false) { 

return;
}
for (Integer integer : vector) { 

System.out.print(integer);
}
System.out.println();
}
for (int i = 2; i <= N; i++) { 

if (isUsed[i]) { 

continue;
}
int temp = vector.get(n - 1) + i;
// 剪枝
if (isPri(temp) == false) continue;
vector.add(i);
isUsed[i] = true;
dfs(n + 1);
isUsed[i] = false;
Integer lastElement = vector.lastElement();
vector.remove(lastElement);
}
}
static boolean isPri(int n) { 

int ans = n & 1;
if (ans == 0) { 

return false;
} else { 

return true;
}
}
}