Snapchat - 2D矩阵的combination

ref: 面筋贴

给一个整数n和一个整数m，n表示正方形边长，正方形初始值全为0。 比如 n=3,代表初始是这样的正方形：

000
000
000

若m=2，代表将其中的2个元素翻转为1，打印出可能得到的所有正方形： 比如

011
000
000

或

000
110
000

。。。

我用backtracking做的，但是时间复杂度没有答好，估计是跪这里了。 follow up是 生成的正方形中， 011 000 000 和 000 000 011 这种对称的正方形视为重复的，如何对之前的结果进行去重。

其实就是一个combination

public List<List<String>> generate(int n, int m) {
    List<List<String>> res = new ArrayList<>();
    char[][] board = new char[n][n];
    for(int i = 0; i < n; i++) {
        Arrays.fill(board[i], '0');
    }
    helper(res, board, n, m, 0, 0);
    return res;
}

private void helper(List<List<String>> res, char[][] board, int n, int m, int cnt, int index) {
    if(cnt == m) {
        List<String> curRes = new ArrayList<String>();
        for(int i = 0; i < n; i++) {
            curRes.add(new String(board[i]));
        }
        res.add(curRes);
        return;
    }
    for(int i = index; i < n * n; i++) {
        int row = i / n;
        int col = i % n;
        board[row][col] = '1';
        helper(res, board, n, m, cnt + 1, i + 1);
        board[row][col] = '0';
    }
}

检查重复，用的是笨方法，把res设成Set。每次往set里面添加的时候翻转一下然后再添加

if(cnt == m) {
    List<String> cur = Arrays.stream(board).map(String::valueOf).collect(Collectors.toList());
    List<String> reverse = new LinkedList<>(cur);
    Collections.reverse(reverse);
    if (!res.contains(cur) && !res.contains(reverse)) {
        res.add(cur);
    }
    return;
}