c++ - 打印 int > 0 的总和

Question

给定一个数字 S ( int > 0 ) 和 n (int > 0 )，打印 len n 的所有不同子集，其总和为 S。 对于 S = 7 和 n = 3，输出如下，输出必须降序:

5 + 1 + 1
4 + 2 + 1 
3 + 3 + 1
3 + 2 + 2

这是我到目前为止尝试过的:

vector<vector<int> > partitions(int X, int Y)
{
    vector<vector<int> > v;
    if (X <= 1 && X <= X - Y + 1)
    {
        v.resize(1);
        v[0].push_back(X);

        return v;
    }
    for (int y = min(X - 1, Y); y >= 1; y--)
    {
        vector<vector<int> > w = partitions(X - y, y);
        for (int i = 0; i<w.size(); i++)
        {
            w[i].push_back(y);
            v.push_back(w[i]);
        }
    }
    return v;


}

int main()
{
    vector<vector<int> > v = partitions(7, 3);
    int i;
    for (i = 0; i<v.size(); i++)
    {
        int x;
        for (x = 0; x<v[i].size(); x++)
            printf("%d ", v[i][x]);
        printf("\n");
    }
}

矩阵中的第一个元素是s-n+1并且全1直到求和，或者如果s-n+1等于s，则n为1，所以只有s是解.

p.s : 不知道这个问题有没有具体的名字

Answer 1

这可能不是您问题的最佳解决方案，因为它不是基于动态规划的解决方案。在这种情况下，我使用递归来填充一个数组，直到我将所需的数字减少到 0。在这个解决方案中，每个组合都将按元素的递增顺序存储，因此我们可以防止已经计算出的解决方案的排列。

#include <iostream>
void findCombinationGivenSize(int numbersArray[], int index, int num, int reducedNum, int maxNum){
    if (reducedNum < 0)
        return; // this is our base case
    if (reducedNum == 0 && index == maxNum){ // both criteria were attended: 
                                           //the sum is up to num, and the subset contain maxNum numbers
        for (int i = index - 1; i>=0; i--)
            std::cout<< numbersArray[i] << " + ";
        // here we will have a problem with an extra '+' on the end, but you can figure out easily how to remove it :)
        std::cout<<std::endl;
        return;
    }
    // Find the previous number stored in arrayNumber[]
    int prev;
    if(index == 0)
        prev = 1;
    else
        prev = numbersArray[index-1];
    for (int k = prev; k <= num; k++){
        // next element of array is k
        numbersArray[index] = k;
        // call recursively with reduced number
        findCombinationGivenSize(numbersArray, index + 1, num,reducedNum - k, maxNum);
    }
}
void findCombinations(int number, int maxSubset){
    int arrayNumbers[number];
    findCombinationGivenSize(arrayNumbers, 0, number, number, maxSubset);
}

int main(){
    int number = 7;
    int maxPartitions = 3;
    findCombinations(number, maxPartitions);
    return 0;
}