c++ - 我的程序有什么方法可以制作任何给定大小的子集？

Question

你好，那里的程序员我面临一个问题

#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!!";
    }
}

如果我得到与用户输入(con)相匹配的结果，则必须制作数组的子集并将其单独添加({1,2} = 1 + 2)，输出将为是或否。现在我面临的问题是我不知道如果用户输入的数组大小为4，那么用户输入将给出多少大小，将需要4个循环。我的子程序在任何大小的数组上都能工作吗
附:抱歉我的英语不好

Answer 1

这是一个递归实现函数的简单示例:

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)实现，因此当您处理较大尺寸的数组时，它将非常慢(并且由于这是递归操作，容易导致堆栈溢出)。