所有元素必须用到的子集组合问题
给定一个数组,要求返回其所有可能的子集组合,其中每个组合必须包含数组中的所有元素。
解决方案
以下 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']] ]