一个所有元素都必须用到的子集组合问题？

  • Z时代
  • 2024-02-12
  • 分类：IT

例如:
给定一个数组[A]，返回[A] 1种结果
给定一个数组[A,B] 返回 [A] [B] 和 [A,B] 2种结果
给定一个数组[A,B,C] 返回:
[A] [B] [C]
[A,B] [C]
[A,C] [B]
[A] [B,C]
[A,B,C]
5种结果

要求就是组合里的所有元素必须都要用到,不考虑顺序 例如 [A,B] 和 [B,A] 是一种结果

回答：

用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);
  }
}
//取子集一半项的差集，因为[[A],[B,C]]认为等同于[[B,C],[A]]
//返回子集和差集的，数组就是题目要求的结果
//单独处理每个单项结果
function generateDiffSets(arr,b){
  var result=[]
  for(var i=0;i<b.length/2;i++){
    //console.log("ddd",arr)
    var diffs = arr.filter(function(v){ 
      return b[i].indexOf(v) == -1
    })
    //console.log(b[i],diffs)
    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)

回答：

import java.util.*;
public class Combination {
    public static List<List<String>> generateCombinations(String[] values) {
        List<List<String>> result = new ArrayList<>();
        if (values == null || values.length == 0) {
            return result;
        }
        List<String> list = new ArrayList<>();
        helper(values, list, 0, result);
        return result;
    }
    private static void helper(String[] values, List<String> list, int start, List<List<String>> result) {
        if (!list.isEmpty()) {
            result.add(new ArrayList<>(list));
        }
        for (int i = start; i < values.length; i++) {
            list.add(values[i]);
            helper(values, list, i + 1, result);
            list.remove(list.size() - 1);
        }
    }
    public static void main(String[] args) {
        String[] values = {"A", "B", "C"};
        List<List<String>> result = generateCombinations(values);
        for (List<String> combination : result) {
            System.out.println(combination);
        }
        System.out.println("Total " + result.size() + " combinations.");
    }
}

以上是 一个所有元素都必须用到的子集组合问题？ 的全部内容， 来源链接： utcz.com/p/945110.html

回到顶部