如何高效地获取数组所有子集及其与子集一半项的差集？

所有元素必须用到的子集组合问题

给定一个数组，要求返回其所有可能的子集组合，其中每个组合必须包含数组中的所有元素。

解决方案

以下 javascript 代码提供了针对此问题的解决方案，并可以轻松转换为 java：

const arr = ['a', 'b', 'c'];

// 获取所有子集
function generatesubsets(arr, subset = [[]]) {
  if (arr.length === 0) {
    return subset;
  } else {
    const current = arr[0];
    const newsubset = [];
    subset.foreach(sub => {
      newsubset.push(sub.concat(current), sub);
    });
    return generatesubsets(arr.slice(1), newsubset);
  }
}

// 取子集一半项的差集
// 返回子集和差集的数组即为题目要求的结果
// 单独处理每个单项结果
function generatediffsets(arr, b) {
  var result = [];
  for (var i = 0; i < b.length / 2; i++) {
    var diffs = arr.filter(function(v) {
      return b[i].indexof(v) == -1
    })
    result.push([b[i], diffs])
  }

  // 添加单项结果
  var t = arr.map((i) => {
    return [i]
  })

  result.push(t)

  return result
}

var subsets = generatesubsets(arr)
var results = generatediffsets(arr, subsets)

console.log(results)

示例结果：

[
  ['A', ['B', 'C']],
  ['B', ['C', 'A']],
  ['C', ['A', 'B']],
  ['A', ['B']],
  ['B', ['C']],
  ['C', ['A']],
  [['A'], ['B', 'C']],
  [['B'], ['C', 'A']],
  [['C'], ['A', 'B']],
  [['A'], ['B']],
  [['B'], ['C']],
  [['C'], ['A']]
]