У меня есть набор S, подобный этому [00 01 10 11]
, и элемент E как 11
. Я хочу узнать количество подмножеств этого множества, сумма цифр которых больше или равна сумме цифр элемента E.
Например, в этом случае ответ равен 10. 10 наборов, удовлетворяющих ограничениям, таковы:
00 01 10 11 // Sum is 3 which is greater than 2 (sum of digits of E)
00 01 11
00 10 11
01 10 11
00 11
01 11
10 11
11
00 01 10
01 10
Сумма всех цифр вышеуказанных подмножеств больше или равна 2 (сумма цифр E).
Я попробовал следующее
public static void main(String[] args) {
Set<String> inputSet = new HashSet<String>();
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();// specifies the length of the digts in the set.
for (long i = 0 ; i < N; i++) {
inputSet.add(sc.next());
}
long sum = 0;
String E = sc.next();//
sc.close();
for (String str : E.split("(?!^)")) {
sum = sum + Integer.parseInt(str);
}
List<Set<String>> subSets = new ArrayList<Set<String>>();
for (String addToSets : inputSet) {
List<Set<String>> newSets = new ArrayList<Set<String>>();
for (Set<String> curSet : subSets) {
Set<String> copyPlusNew = new HashSet<String>();
copyPlusNew.addAll(curSet);
copyPlusNew.add(addToSets);
newSets.add(copyPlusNew);
}
Set<String> newValSet = new HashSet<String>();
newValSet.add(addToSets);
newSets.add(newValSet);
subSets.addAll(newSets);
}
long sum1;
long count = 0;
for (Set<String> set : subSets) {
sum1 = 0;
for (String setEntry : set) {
for (String s : setEntry.split("(?!^)")){
sum1 = sum1 + Integer.parseInt(s);
}
}
if (sum == sum1 || sum1 > sum)
count = count+1;
}
System.out.println(count);
}
Ограничения 1 ‹= N ‹= 10^5
1 <= M <= 20
Приведенный выше подход не будет работать для размеров наборов в диапазоне 105. Пожалуйста, помогите обеспечить эффективный подход для этого. Спасибо!