# 672. Bulb Switcher II

T: O(presses \* initStatus), initStatus is (1 << n) -1 (not sure

````java
```java
class Solution {
    public int flipLights(int n, int presses) {
        if (n > 6) { // 2, 3 最大公倍數是 6
            n = 6;
        }
        int initStatus = (1 << n) -1;
        int[] mask = getMask(n);
        boolean[][] visited = new boolean[presses+1][initStatus+1];

        dfs(initStatus, visited, 0 ,presses, mask);

        int result = 0;
        for (int i = 0; i < visited[presses].length; i++) {
            if (visited[presses][i]) {
                result++;
            }
        }
        return result;
    }
    private void dfs(int status, boolean[][] visited, int pressCount, int presses, int[] mask) {
        if (pressCount == presses + 1) {
            return;
        }
        if (visited[pressCount][status]) {
            return;
        }
        visited[pressCount][status] = true;
        for (int m : mask) {
            dfs(status ^ m, visited, pressCount + 1, presses, mask);
        }
    }

    private int[] getMask(int n) {
		int s = (1 << n) - 1; // 1
        int[] mask = new int[4];
        mask[0] = s;
        for (int i = 0; i < n; i++) { // 0,1,2,3
            if (i % 2 == 0) {
                mask[1] += 1;
            }
            if (i != n-1) {
                mask[1] = mask[1] << 1; // 10. , 0
            }
        }
        for (int i = 0; i < n; i++) { // 0, 1
            if (i % 2 == 1) {
                mask[2] += 1;
            }
            if (i != n-1) {
                mask[2] = mask[2] << 1; // 01.  , 1
            }
        }
        if (n <= 3) {
            mask[3] = 1;
        } else {
            mask[3] = 9;
        }
		return mask;
    }
}
/*
different possible status:
is 
initial status -> all on -> s

with 4 mask
mask1 = s

(from right side)
mask2 = 010101
mask3 = 101010
mask4 = 001001 


*/
```
````

