подсчитать все подмножества данного массива с суммой, равной данной сумме - PullRequest
Новая
       72

подсчитать все подмножества данного массива с суммой, равной данной сумме

0 голосов
/ 14 марта 2020

что я могу сделать, чтобы оптимизировать этот код, если язык будет c ++, мне будет легче понять.

Учитывая массив целых чисел и сумму, задача состоит в том, чтобы подсчитать все подмножества данный массив с суммой, равной данной сумме. Ввод: arr [] = {2, 3, 5, 6, 8, 10}, сумма = 10, подмножества -> {5 2 3}, {2 8}, {10}, выход: 3 Ввод: arr [ ] = {1, 2, 3, 4, 5}, сумма = 10, подмножества -> {4 3 2 1}, {5 3 2}, {5 4 1}, Выход: 3) 

#include<bits/stdc++.h>

using namespace std;


string binary_string(int i,int len){

    string res="";
    int mod =0;

        while(i>0){
        mod = i%2;
        res+=to_string(mod);
        i/=2;
    }

    int n = res.length();

    if(n!=len){
        while(n!=len){
            res.append("0");
            n++;

        }


         return res;
    }



    return res;
}

int main()
{
   int t;
   cin>>t;

   while(t--){
    string binary;//,subseq;
    int n,k,count=0,sum,val;
    cin>>n;

    vector<int>vect;

    for(int i=0;i<n;i++){
        cin>>k;
        vect.push_back(k);
    }
    cin>>val;


    int bits_range = (int)pow(2,n) - 1;



    //cout<<"SUBSETS ARE :"<<endl;
    for(int i=0;i<=bits_range;i++){
        binary=binary_string(i,n);
        sum=0;
        for(int i=binary.length()-1;i>=0;i--){
            if(binary[i]=='1'){
                //subseq+=to_string(vect[i]);
                sum+=vect[i];

            }

        }
        if(sum==val){
            count++;
            //cout<<subseq<<endl;
            //subseq="";
        }
        //subseq="";
    }

        cout<<count<<endl;
   }



}

1 Ответ

0 голосов
/ 14 марта 2020

Вы можете отсортировать массив, а затем использовать идею, аналогичную Технике с двумя указателями . Сложность O (NlogN) или линейная, если вы можете сортировать по линейному времени.

Редактировать: Я лучше объясню, что я имею в виду. vect теперь отсортированная версия массива. partial является частичной суммой подмассива [a, b). 

int partial = 0;
int a = 0, b = 0;
int count = 0;
while (true) {
  if (partial == sum) {
    count++;
    a++;
  } else if (partial < sum) {
    if (b == vect.size()) {
      break;
    }
    partial += vect[b];
    b++;
  } else {
    partial -= vect[a];
    a++;
  }
}

Обратите внимание, что оба значения a и b могут только увеличиваться, поэтому цикл имеет максимум 2*vect.size() итераций Таким образом, сложность является линейной. После этого count содержит ответ.

Вам следует убедиться, что этот код работает правильно, но я надеюсь, что вы поняли из него идею.

...