时间戳

首页 > 解决方案 > 有没有办法让我的程序可以制作任何给定大小的子集？

c++ - 有没有办法让我的程序可以制作任何给定大小的子集？

问题描述

我面临一个问题。

#include <iostream>

using namespace std;
bool Check(int arr[], int size, int con)
{
    for (int i = 0; i < size; i++)
    {
        if (arr[i] == con)
        {
            return true;
        }
        for (int j = i+1; j < size;j++)
        {
            if (arr[i]+arr[j] == con)
            {
                return true;
            }
            for (int k = j + 1; k < size; k++)
            {
                if (arr[i] + arr[j] + arr[k] == con)
                {
                    return true;
                }
                for (int l = k + 1; l < size;l++)
                {
                    if (arr[i] + arr[j] + arr[k] + arr[l] == con)
                    {
                        return true;
                    }
                }
            }
        }
    }
}


int main()
{
    int size;
    int con;
    cout << "Enter desire size of array" << endl;
    cin >> size;
    cout << "ENter number" << endl;
    cin >> con;
    int *arr = new int[size];
    for (int i = 0; i < size; i++)
    {
        cin >> *(arr + i);
    }
    if (Check(arr, size, con) == true)
    {
        cout << "YESSS!!";
    }
    else
    {
        cout << "NOOO!!";
    }
}

我必须制作数组的子集并单独添加它们（{1,2} = 1+2）。如果我得到与用户输入 (con) 匹配的结果，则输出将为 YES 或 NO。

现在我面临的问题是我不知道用户将输入多少尺寸。如果他/她输入数组的大小为 4，则需要 4 个循环。我的子程序是否适用于每种大小的数组？

标签： c++data-structures

解决方案

这是您的函数的递归实现的简单示例：

bool Check(int *arr, int size, int con, int curr_sum = 0)
{       
    for (int i = 0; i < size; i++)
    {
        int new_sum = curr_sum + arr[i];
        if (new_sum == con
            || Check(arr + i, size - i, con, new_sum))
        {
            return true;
        }
    }
    return false;
}

这是它的工作原理...

我们传递一个curr_sum参数，该参数保存父递归的总和。当前的递归将通过将其所有索引添加到其中，寻找curr_sum + arr[i] == con. 如果不是，那么我们将获取新的总和 ( curr_sum + arr[i]) 并对其进行另一轮递归，该递归从我们当前正在查看的索引之后的索引开始。

请注意：这是您正在使用的 O(n^2) 实现，因此当您处理较大的数组时，它会非常慢（并且因为这是递归，容易堆栈溢出）。

推荐阅读