计算给定数组的所有子集的总和等于给定总和

Question

我可以做些什么来优化此代码，如果语言是c ++，对我来说更容易理解。

给定一个整数和一个和的数组，任务是计算给定数组的所有子集，其和等于给定的和。输入：arr [] = {2，3，5，6，8，10}，sum = 10，子集为-> {5 2 3}，{2 8}，{10}，输出：3输入：arr [] = {1,2,3,4,5}，sum = 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;
   }



}

Answer 1

您可以对数组进行排序，然后使用类似于Two-Pointer Technique的想法。复杂度为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包含答案。

您应该检查该代码是否正常运行，但希望您从中了解这个想法。