1

我需要一些关于 C++ 问题的帮助。用户输入他想输入的数字，然后输入所有数字和一个特殊值。程序必须找到并写入总和等于特殊值的所有数字组合。例子：

输入

12
1 5 7 3 10 8 9 2 4 6 11 13
15

输出：

4 11
2 13
9 6
9 2 4
3 2 4 6
3 8 4
3 10 2
7 2 6
7 8
5 4 6
5 8 2
5 10
5 7 3
1 8 6
1 8 2 4
1 10 4
1 3 11
1 3 9 2
1 7 3 4
1 5 9
1 5 3 6
1 5 3 2 4
1 5 7 2

代码

这是编写包含 2 个元素的所有组合的代码：

#include <iostream> 
using namespace std;

int main(int argc, const char * argv[])
{
    int size;
    cout << "Enter size: ";
    cin >> size;
    int *numbers = new int[size];
    cout << "Enter numbers: ";
    for (int i = 0; i < size; i++)
        cin >> numbers[i];
    int target;
    cout << "Enter target: ";
    cin >> target;
    int sum = 0;
    for (int i = 0; i < size-1; i++)
    {
        for (int j = i+1; j < size; j++)
        {
            sum = numbers[i];
            sum += numbers[j];
            if (sum == target)
                cout << numbers[i] << " " << numbers[j] << "\n";
        }
    }
    return 0;
}

如果我用这个替换那个 for 循环，程序将编写包含 3 个元素的所有组合：

for (int i = 0; i < size-2; i++)
{
   for (int j = i+1; j < size-1; j++)
   {
      for (int k = j+1; k < size; k++)
      {
         sum = numbers[i] + numbers[j];
         sum += numbers[k];
         if (sum == target)
         cout << numbers[i] << " " << numbers[j] << " " << numbers[k] << "\n";
       }
    }
}

这是我的问题：如何制作一个编写所有可能组合的程序？

4

1 回答 1

1
  1. 从您的列表中取出第一个数字（例如，1）。
  2. 从您的列表中删除此号码，并将其从您的“目的地”总数中扣除。
  3. 现在您有了一个新列表和一个新的目的地总数。重复。
  4. 如果您的总数超过您的目的地，请跳过当前号码（即，保留列表中的号码，不要更新目的地）并移至下一个。
  5. 如果列表中的剩余项目都不能让您到达目的地，请弹出您添加到目的地总数的最后一个数字，并使用列表中的下一个数字更新它。
  6. 如果您达到您的目标总数，您将拥有原始列表中的一部分数字（大小介于 1 和列表中的元素数量之间），这些数字加起来就是您的预期总数。
于 2012-11-16T14:16:44.803 回答