【练习题】25.找出N个数之和等于M

/*
    题目：
        给定一个target，和一个"有序"数组ra。
    要求：
        从ra中挑选length2个数，使得它们之和等于target;
    说明:
        length2个数中可以出现重复
    
    例子:
        如 a+b+c = 31,a/b/c都来自于[1,3,5,7,9,11,13,15]。
        则
*/



#include<iostream>
#include<vector>
#include<ctime>
using namespace std;

void findCorrectNumbers(int target, int* ra, int length, std::vector<int> result ,int hasCheckedPosition,int length2)
{
    if (hasCheckedPosition>=0)
    {
        //1.从后往前找到小于target的第一个数
        int one = ra[hasCheckedPosition];
    
        //2-1.如果之前累加的值加上这个值依然小于target，考察这个值（分为两种情况）
        if (one < target && result.size()<length2 )
        {
            result.push_back(one);
            //情况1：保留了one，所以剩下的数只要和能够达到target-one就可以了
            findCorrectNumbers(target - one, ra, length, result,  hasCheckedPosition, length2);
            if (result.size()>0)
                result.pop_back();
            //情况2：不保留one，所以剩下的数之和依然要达到target
            findCorrectNumbers(target, ra, length, result, hasCheckedPosition-1, length2);
        }
        //2-2.如果当前值刚好等于结果，就打印，然后递归返回，看后面还有满足的没
        if (one == target && result.size()<length2)
        {
            
            
            result.push_back(one);
            if (result.size() == length2)
            {
                std::cout <<std::endl<< "找到一组值：" << std::endl;
                for (int j = 0; j < result.size(); j++)
                    std::cout << result.at(j) << " ";
            }
            if (result.size()>0)
                result.pop_back();
            findCorrectNumbers(target, ra, length, result, hasCheckedPosition-1, length2);
        }
        //如果这个数加上上currentTotal大于目标值，就考察前一个
        if (one > target)
        {
            findCorrectNumbers(target, ra, length, result, hasCheckedPosition - 1, length2);
        }
    }
        
}
 
//-------Main-----------------------
 

int main()
{
    int target =31;
    std::vector<int> result;
    int length = 11;
    int length2 = 3;
    int array[11] = {1,2,3,5,7,9,11,13,15,17,19};
    cout << "目标数值（target）:";
    cin >> target;
    cout << "限定解长度（length2）：";
    cin >> length2;
    clock_t start_time = clock();
    {
        //被测试代码
        for (int i = 0; i < length; i++)
        for (int j = 0; j < length; j++)
        for (int x = 0; x < length; x++)
        {
            if (array[i] + array[j] + array[x] == target)
                cout << "i==" << array[i] << ",j==" << array[j] << ",x==" << array[x] << endl;
        }
    }
    clock_t end_time = clock();
    cout << "暴力测试耗时: " << static_cast<double>(end_time - start_time) / CLOCKS_PER_SEC * 1000 << "ms" << endl;//输出运行时间
    clock_t start_time2 = clock();
    {
        //被测试代码
        findCorrectNumbers(target, array, length, result, length - 1, length2);
    }
    clock_t end_time2 = clock();
    cout <<endl<< "回溯法求解耗时: " << static_cast<double>(end_time2 - start_time2) / CLOCKS_PER_SEC * 1000 << "ms" << endl;//输出运行时间
    
    return 0;
}
           

附上结果：