寻找和为定值的多个数

小咪咪 2022-08-07 13:59 129阅读 0赞

输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,

使其和等于 m ,要求将其中所有的可能组合列出来。

两种方法，其实本质都是递归算法结构，回溯算法思想。

方法一：

#include<iostream>
    #include<list>
    using namespace std;
    
    static int count = 0;
    list<int>list1;
    void SumOfkNumber(int sum, int n)
    {
        // 递归出口
        if (n <= 0 || sum <= 0)
            return;
    
        // 输出找到的结果
        if (sum == n){
            // 反转list
            list1.reverse();
            for (list<int>::iterator iter = list1.begin(); iter != list1.end(); iter++)
                cout << *iter << " + ";
            cout << n << endl;
    		count++;
            list1.reverse();//此处还需反转回来
        }
    
        list1.push_front(n);      //典型的01背包问题
        SumOfkNumber(sum - n, n - 1);   //“放”n，前n-1个数“填满”sum-n
        list1.pop_front();
        SumOfkNumber(sum, n - 1);     //不“放”n，n-1个数“填满”sum
    }
    
    //int main(){
    //	SumOfkNumber(15, 100);
    //	cout<<count<<endl;
    //}

方法二，其实也是去试，不过有了 回溯 中的 剪枝 操作。

//输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,  
    //使其和等于 m ,要求将其中所有的可能组合列出来。  
      
    #include <stdio.h>  
    #include <stdlib.h>  
    #include <memory.h>  
      
    /**  
     * t为目前的加和，k为要考虑的那个值，r为从k开始到n的所有加和，M为目标值
     */  
    static int count=0;
    void sumofsub(int t, int k ,int r, int& M, bool& flag, bool* X)  
    {  
        X[k] = true;   // 选第k个数  
        if (t + k == M) // 若找到一个和为M，则设置解向量的标志位，输出解  
        {  
            flag = true;  
            for (int i = 1; i <= k; ++i)  
            {  
                if (X[i] == 1)  
                {  
                    printf("%d ", i);  
                }  
            }
    		count++;
            printf("\n");  
        }  
        else  
        {   // 选k,而且严格意义上是k足够小，有再加的余地 
            if (t + k + (k+1) <= M)  
            {  
                sumofsub(t + k, k + 1, r - k, M, flag, X);  
            }  
            // 若不选第k个数，那么剩下的那些数的加和必须大于或等于M，而且k+1还得小于M-t。  
            if ((t + r - k >= M) && t+(k+1) <= M)  
            {  
                X[k] = false;  
                sumofsub(t, k + 1, r - k, M, flag, X);  
            }  
        }  
    }  
      
    void search(int& N, int& M)  
    {  
        // 初始化解空间  
        bool* X = (bool*)malloc(sizeof(bool) * (N+1));  
        memset(X, false, sizeof(bool) * (N+1));  
        int sum = (N + 1) * N * 0.5f;  
        if (1 > M || sum < M) // 预先排除无解情况  
        {  
            printf("not found\n");  
            return;  
        }  
        bool f = false;  
        sumofsub(0, 1, sum, M, f, X);  
        if (!f)  
        {  
            printf("not found\n");  
        }  
        free(X);  
    }  
      
    int main()  
    {  
        int N, M;  
        printf("请输入整数N和M\n");  
        scanf("%d%d", &N, &M);  
        search(N, M); 
    	printf("%d\n", count);
        return 0;  
    }

本文的代码摘自 [http://blog.csdn.net/v\_july\_v/article/details/6419466][http_blog.csdn.net_v_july_v_article_details_6419466]  
但是，感觉方法二的注释，原作者的表达意思实在是令人费解，也许是我能力有限。所以，改成了本人自己的愚见，希望有助于个人理解。

[http_blog.csdn.net_v_july_v_article_details_6419466]: http://blog.csdn.net/v_july_v/article/details/6419466