c++ - 了解子集之和

Question

我刚开始在大学学习回溯算法。不知何故，我设法为子集求和问题编写了一个程序。工作正常，但后来我发现我的程序没有给出所有可能的组合。

例如:目标总和可能有一百种组合，但我的程序只给出了 30 种。 这是代码。如果有人能指出我的错误是什么，那将是一个很大的帮助。

int tot=0;//tot is the total sum of all the numbers in the set.
int prob[500], d, s[100], top = -1, n; // n = number of elements in the set. prob[i] is the array with the set.
void subset()
{
    int i=0,sum=0; //sum - being updated at every iteration and check if it matches 'd'
    while(i<n)
    {
        if((sum+prob[i] <= d)&&(prob[i] <= d)) 
        {
            s[++top] = i;
            sum+=prob[i];
        }
        if(sum == d) // d is the target sum 
        {
            show(); // this function just displays the integer array 's'
            top = -1; // top points to the recent number added to the int array 's'
            i = s[top+1];
            sum = 0;
        }
        i++;
        while(i == n && top!=-1)
        {
            sum-=prob[s[top]];
            i = s[top--]+1;
        }
    }
}

int main()
{
    cout<<"Enter number of elements : ";cin>>n;
    cout<<"Enter required sum : ";cin>>d;
    cout<<"Enter SET :\n";
    for(int i=0;i<n;i++)
    {
        cin>>prob[i];
        tot+=prob[i];
    }
    if(d <= tot)
    {
        subset();
    }
    return 0;
}

当我运行程序时:

Enter number of elements : 7
Enter the required sum : 12
Enter SET : 
4 3 2 6 8 12 21

SOLUTION 1 : 4, 2, 6
SOLUTION 2 : 12

虽然4、8也是解，但是我的程序没有显示出来。 输入数量为 100 或更多时，情况更糟。至少会有 10000 种组合，但我的程序显示 100。

我试图遵循的逻辑:

1. 将主 SET 的元素纳入一个子集，只要 子集的总和保持小于或等于目标总和。
2. 如果将特定数字添加到子集总和使得它 比目标大，它不接受它。
3. 一旦到达终点 的集合，并且没有找到答案，它删除了最 最近从集合中取出号码并开始查看号码 在最近号码删除的位置之后的位置。 (因为我在数组“s”中存储的是 从主 SET 中选择号码)。

Answer 1

由于步骤 1 中的“只要”子句，您将要找到的解决方案取决于集合中条目的顺序。

如果您在没有让您超过目标的情况下进行输入，例如，一旦您输入了'4' 和 '2', '8' 将带你超过目标，所以只要 '2' 在 '8' 之前在你的集合中，你就永远不会得到带有 '4' 和 '8' 的子集。

您应该增加跳过添加条目的可能性(或将其添加到一个子集而不是另一个子集)或更改集合的顺序并重新检查它。