寻找和为定值的多个数

题目描述：

输入两个整数 n 和 sum ，从数列 1，2，3 ....... n 中随意取几个数，使其和等于 sum，要求将其中所有的可能组合列出来。

分析和解法：

解法一：n 问题转化为 n-1 问题

注意到取 n，和不取 n 的区别即可，考虑是否取第 n 个数的策略，可以转化为一个和前 n-1 个数相关的问题。

• 如果取第 n 个数，那么问题就转化为 “ 取前 n-1 个数使得它们的和为 sum-n ”，对应的代码语句就是 sumOfkNumber(sum - n, n - 1)；
• 如果不取第 n 个数，那么问题就转化为 “ 取前 n-1 个数使得他们的和为 sum ”，对应的代码语句为sumOfkNumber(sum, n - 1);

源代码如下：

#include <iostream>
#include <list>

using namespace std;

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;
        list1.reverse();  //此处还需反转回来 
    } 
    
    list1.push_front(n);  //典型的 0/1 背包问题
    SumOfkNumber(sum - n, n - 1);  //“放”n，前n-1个数“填满”sum-n
    list1.pop_front();
    SumOfkNumber(sum, n - 1);  //不“放”n，n-1个数“填满”sum 
}

int main()
{
    int a[100];
    int n;
    cin >> n;
    int sum;
    cin >> sum;
    SumOfkNumber(sum, n);
    return 0;
}

分析：递归调用，注意语句先后顺序。时间复杂度为 O（n ^ 2）。反转链表输出是为了体现思考过程，即函数执行过程。

解法二：回溯 + 剪枝

这个问题属于子集和问题（也是背包问题），故可采用回溯 + 剪枝的方法，定义 X 数组是解向量，t = ∑(1, ..., k-1)Wi * Xi， r = ∑(k, .., n)Wi，且

• 若 t + Wk + W(k+1) <= M,则 Xk = true，递归左儿子 (X1,X2,..,X(k-1),1)；否则剪枝；
• 若 t + r - Wk >= M && t + W(k+1) <= M,则置 Xk = 0，递归右儿子 (X1,X2,..,X(k-1),0)；否则剪枝；

本题中 W 数组就是 (1,2,..,n) ，所以直接用 k 代替 WK 值。
源代码如下：

#include <iostream>
#include <cstring>
#include <cstdlib>

using namespace std;

//输入 t 和 r ，尝试 Wk
void SumOfkNumber(int t, int k, int r, int& M, bool& flag, bool* X)
{
    X[k] = true;    //选第 k 个数
    if (t + k == M)
    {
        flag = true;
        for (int i = 1; i <= k; i++)
        {
            if (X[i] == 1)
                cout << i << " " ;
        }
        cout << endl;
    }
    else 
    {
        //若第 k+1 个数满足条件，则递归左子树
        if (t + k + (k + 1) <= M)
            SumOfkNumber(t + k, k + 1, r - k, M, flag, X);
        //若不选第 k 个数，选第 k+1 个数满足条件，则递归右子树
        if ((t + r - k >= M) && (t + (k + 1) <= M))
        {
            X[k] = false;
            SumOfkNumber(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)  //预先排除无解情况
    {
        cout << "not found" << endl;
        return; 
    } 
    bool f = false;
    SumOfkNumber(0, 1, sum, M, f, X);
    if (!f)
        cout << "not found" << endl;
    free(X); 
}

int main()
{
    int n;
    cin >> n;
    int sum;
    cin >> sum;
    Search(n, sum);
    return 0;
}

分析：这个算法比较好理解，但是函数实现过程有点费解。

特别注意：

• 这种问题都是从后向前考虑，递归向下求解

参考资料：《编程之法》The Art of Programming By July