【算法练习】无聊的逗（二进制表示组合）

一种朴素的想法是用搜索求木棍的组合，再去比较剩下木棍的组合，剩下木棍的组合中不能有当前木棍组合中的木棍，问题在于：在找剩下木棍的组合时，由于不能包含当前组合中的木棍，不能容易求出来。

假设有4根木棍，用二进制0000表示，0代表不取当前木棍，1代表取当前木棍，0001代表取第一根木棍，0011代表取第一二根木棍，以此类推，会产生多少种组合？2^4 = 16（包含了全零）。

通过对1移位，即可实现木棍的选取，1 << 0（选第一根），1 << 1（选第二根），16种组合分别为：0000、0001、0011…1111，0001与木棍的选取相“与”，例如：0001与(1 << 0) = 1，说明当前组合应该包含该木棍，再例如：0011与(1 << 0) = 1，0011与(1 << 1) = 1，说明当前组合0011应该包含第一根、第二根木棍。这样就可以在确定组合的情况下，选择满足组合的木棍。

上面的步骤都与dfs搜索没什么区别，就是找不同组合，dfs搜索也可以实现，关键是下面：不同组合的比较，如何保证不重复取木棍？

看看两个组合之间有什么关系？0001与0011 = 0001，0011与0111 = 0011，0010与0001 = 0000，两个组合相与，如果结果为0，说明两个组合没有重复选取木棍，这样就可以保证不重复选取木棍。

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[] sticks = new int[n];
        for (int i = 0; i < n; i++) {
            sticks[i] = scan.nextInt();
        }
        int pow = (int)Math.pow(2, n);
        int[] v = new int[pow];
        // 外层循环遍历2^n种组合方式：从0000 - 1111
        for (int i = 0; i < (1 << n); i++) {
            // 内层循环遍历n根木棍
            if (i == 0) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                // 选择当前组合应该选择的木棍
                // 注意只能确定值 != 0，不能确定是哪个数！
                if ((i & (1 << j)) != 0) {
                    v[i] += sticks[j];
                }
            }
        }
        // 遍历每种组合，在不重复使用木棍的情况下，选择最长的
        int max = -1;
        for (int i = 0; i < (1 << n); i++) {
            if (i == 0) {
                continue;
            }
            for (int j = 0; j < (1 << n); j++) {
                if ((i & j) == 0 && v[i] == v[j]) {
                    max = Math.max(max, v[i]);
                }
            }
        }
        System.out.println(max);
    }
}

使用二进制，可以很快的解决组合、部分选择的问题。