DFS回溯题：奇偶交错排列

问题：

思路：

使用DFS回溯法解决
关于DFS回溯法，它并不是一种具体的算法，应该说是一种思想
DFS的基本思想：
1：一条路走到底。
2：只有当前状态不存在任何后继状态时，才返回至上一层状态(也就是从哪来回哪去)
3：一旦从该状态返回，说明该状态及其后继状态都已经访问过，故无需再次访问。

对于本题，要求求解相邻数字奇偶性不同的全排列。我们可以使用dfs函数逐位遍历所有情况，由于每个数字在排列中只能出现一次，因此我们使用visit[]数组保存一个数字是否出现过。又因为相邻数字要求奇偶性不同，我们需保存上一位数字的奇偶性，以决定当前位可选哪些数字。
选取当前位数字时，从1~n中选择满足条件的数字，之后调用下一位的dfs函数，dfs函数返回，即表示当前分支已走完，将当前位数字的visit重置，即回溯到上一层状态

dfs函数的参数有保存每位数字的数组array，当前位的下标now，上一位数字的奇偶性last，题目给定的n，以及visit数组。设now从1开始，当now == n+1时，表示已经得到一个排列，dfs返回

需注意的点：

判断i的奇偶性使用( i & 1 )，即i和1相与，若i为奇数，和1相与得到1，否则得0

代码：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n;
        int[] array = new int[12];
        int[] visit = new int[12];
        while (scanner.hasNextInt()) {
            Arrays.fill(visit, 0);
            n = scanner.nextInt();
            dfs(array, 1, -1, n, visit);
        }

    }

    static void dfs(int[] array, int now, int last, int n, int[] visit) {
        int i;
        if (now == n + 1) {
            for (i = 1;i <= n;i++) {
                System.out.print(array[i] + " ");
            }
            System.out.print('\n');
        }
        for (i = 1;i <= n;i++) {
            if (visit[i] == 0 && last != (i & 1)) {
                array[now] = i;
                visit[i] = 1;
                dfs(array, now + 1, i & 1, n, visit);
                visit[i] = 0;
            }
        }
    }
}