与えられた整数配列、与えられた整数値のすべてのサブセットを出力

2746 ワード

これは私が学校のフォーラムである同級生を見て、書いたツールです.しかし、当時、彼はpythonで書いたので、注釈や説明はなく、正直に言って、私は理解していませんでした.しかし、主な機能は、整数配列があり、それから数mがあり、整数配列の中で、すべての和がmに等しい組み合わせを見つけて出力することです.
例えば配列{1,5,3,7,6,4,2},m=7,
出力:1 6
          3 4
          7
          1 2 4
          2 5
このことは長い間考えていた.そして昨日の100-21のテーマをしていたとき、突然これに似ているような気がして、それから私は考えに沿って(具体的な考えは100-21を見ることができます)方法を見つけましたが、コードは複雑で、効率が悪いです.何かもっと最適化する方法があるのか分からない.
コードはやはり貼り付けましょう.
/*==========================================*\
               ,      。
   ,   python  ,       ,  
 ,     。       ,       ,
      m,        ,     m  
 ,   。
     {1,5,3,7,6,4,2},m = 7,
  :1 6
	  3 4
	  7
	  1 2 4
	  2 5
\*==========================================*/
#include <iostream>
#include <vector>

using namespace std;

//  
int partition(int *index,int begin,int end){
	int i = begin;
	int j = end;
	int temp;

	while(i<j){
		while(index[i]<index[j]){
			--j;
		}
		if(i<j){
			temp = index[i];
			index[i] = index[j];
			index[j] = temp;
		}
		while(index[i]<index[j]){
			++i;
		}
		if(i<j){
			temp = index[i];
			index[i] = index[j];
			index[j] = temp;
		}
	}
	return i;
}

void quickSort(int *index,int begin,int end){
	if(begin < end){
		int q = partition(index,begin,end);
		quickSort(index,begin,q-1);
		quickSort(index,q+1,end);
	}
}

int binaryFind(int *index,int length,int n){//    
		int i = 0;
		int j = length -1;
		while(i <= j){
			int pIndex = (i+j)/2;
			if(index[pIndex] > n){
				j = pIndex - 1;
			}else if(index[pIndex] < n){
				i = pIndex + 1;
			}else if(index[pIndex] == n){
				return pIndex;//        
			}
		}
		return -1;//    -1
}

bool FindSum(int sum, int *index , int pIndex , vector<int> &vresult)
{
	bool ret = false;
	if (sum<=0||pIndex<0)
		return ret;

	if (sum<=index[pIndex]){
		int flag = binaryFind(index,pIndex+1,sum);
		if(flag >= 0){
			pIndex = flag;
			vresult.push_back(index[pIndex]);
			for (int i=vresult.size()-1;i>=0;i--){
				cout<<vresult[i]<<" ";
			}
			cout<<endl;
			vresult.pop_back();
			ret = true;
		}
	}

	vresult.push_back(index[pIndex]);
	bool res1=FindSum(sum-index[pIndex],index, pIndex-1, vresult);
	vresult.pop_back();
	//cout << "index : " << index[pIndex] << endl;
	bool res2=FindSum(sum,index, pIndex-1,vresult);

	return res1||res2||ret;

}

void Find(int sum, int *index,int length)
{
	vector<int> vresult;
	quickSort(index,0,length-1);//      ,        ,    100-21    
	if(!FindSum(sum,index, length-1 , vresult))
		cout<<" can't get "<<sum<<endl;
}

int main(){
	int index[] ={1,5,7,6,2,100};
	Find(7,index,sizeof(index)/sizeof(int));
	return 1;
}