main.cpp

一个我的数据结构解题集合

#include <iostream>
#include "Vector.h"
#include "IoUtils.h"
using namespace std;

int findCombinations(const Vector<int>& num, int m) {
    int count = 0;		// 解的个数 
    Vector<char> status;
	status.enlarge(num.size());
	status[0] = 0;

	int i = 0;
	int curr_val = 0;
    while(true) {
        while (true) {
			if (status[i] > 1) break;							// 从右子结点返回，直接回溯
			if (status[i] == 0 && curr_val+num[i] <= m) {		// 存在左子树，向左走
				curr_val += num[i];
			} else
			if (status[i] != 1) {								// 存在右子树，向右走
				status[i] = 1;
			}

			if ( ++i < num.size() ) {
				status[i] = 0;								// 下一层从左子树找起，清空status
			} else {
				break;
			}
        }

        if (i == num.size() && curr_val == m) {				// 得到一解，输出 
            for (int j = 0; j < num	.size(); ++j) {
                if (status[j] == 0) cout << num[j] << " ";
            }
            cout << endl;
            ++count;
        }
		
		if (--i < 0) break;									// 遍历结束

		if (status[i] == 0)									// 回溯
			curr_val -= num[i];

		++status[i];
    }
    
    return count; 
}


int main() {
    Vector<int> vec;
	cout << "输入n个不同的正整数，设计一个程序，找出这些正整数的所有组合，\n"
		 << "要求每一个组合中，各数的累加和等于一个给定的正整数m\n"
		 << endl;

	cout << "输入n个正整数，<=0表示结束: ";
	int i;
	while ( (i = getInteger()) > 0 ) {
		vec.pushBack(i);
	}

	cout << "请给定m: ";
	int m = getPositiveInteger();

	int count = findCombinations(vec, m);

    cout << "解的个数: " << count << endl; 

    system("pause"); 

    return 0; 
}