一个整数数组，有n个整数，如何找其中m个数的和等于另外n-m个数的和？

int getSum(int* arr, int len) {
	int sum = 0;
	for (int i = 0; i < len; ++i) {
		sum += arr[i];
	}
	return sum;
}

void difPrint(int* arr, int len, vector<int> vct) {
	cout << vct.size() << " =m 数组: ";
	for (int i = 0; i < vct.size(); ++i) {
		cout << vct[i] << " ";
	}
	cout << endl;

	cout << len - vct.size() << " =n-m 数组: ";
	int vid = 0;
	for (int i = 0; i < len; ++i) {
		if (vct[vid] == arr[i]) {
			vid++;
			continue;
		} else {
			cout << arr[i] << " ";
		}
	}
	cout << endl << endl;
}

//vector<int> result;
void findNumsEqSum(int* arr, int step, int len, int curSum, int sum,
		vector<int> vct) {
	if (!arr || !len || curSum > sum || step == len) {
		return;
	}
	if (sum == curSum) {
		difPrint(arr, len, vct);
	} else {
		vct.push_back(arr[step]);
		findNumsEqSum(arr, step + 1, len, curSum + arr[step], sum, vct);
		vct.pop_back();
		findNumsEqSum(arr, step + 1, len, curSum, sum, vct);
	}

}

巴特西

一个整数数组，有n个整数，如何找其中m个数的和等于另外n-m个数的和？

最新文章

热门文章