c++ - 分区问题的递归函数

Question

问题是找出数组中数字的子集加起来达到特定目标数字的次数。

例如，有两种方法可以对集合{1, 3, 4, 5}进行分区，使剩余元素加起来为5:

• 选择1 和4
• 仅选择5

相比之下，无法对集合 {1, 3, 4, 5} 进行分区以获得 11。

#include "genlib.h"
#include <iostream>

void RecursePart(int[], int, int, int&);
int Wrapper(int[], int, int);


int main() {
    int arr[8] = {1,2,3,4,5,6,7,8};
    cout << Wrapper(arr, 8, 11);
}


void RecursePart(int arr[], int len, int target, int& ctr) {
    if (len == 1) {
        if (arr[0] == target) {
            ctr++;
        }
        return; 
    }

    int sum, temp;
    sum = temp = arr[0];

    for (int j = 1; j < len; j++) {
        if (sum == target) {
            ctr++;
            break;
        }

        sum = sum + arr[j];

        if (sum == target) {
            ctr++;
            sum = temp;
            continue;           
        }

        if (sum > target) {
            sum = temp;
            continue;
        }

        if (sum < target) {
            temp = sum;
            continue;
        }    
    }

    RecursePart(arr + 1, len - 1, target, ctr);
}

int Wrapper(int arr[], int len, int target) {
    int n = 0;
    RecursePart(arr, len, target, n);
    return n;
}

问题是我得到的输出是 1，但是数组中数字的子集加起来为 11 的次数大于 1。我尝试跟踪该算法，并且知道问题所在必须在for循环中。算法会跳过一些求和。我怎样才能解决这个问题？

Answer 1

正如其他人所说，这是子集和问题(NP 完全问题)，这意味着您需要指数时间算法来解决它。
只需查看您的函数，您就可以调用 RecursePart 一次，每次都使用 len-1，然后有一个长度为 n 的 for-loop ，这意味着您的计算量为 O(n^2)。这显然无法解决 O(2^n) 问题。

以下是一个递归解决方案，它创建子集的总和，并尝试查看它们是否达到目标。如果当前子集没有等于目标的选项，则停止当前子集的“创建”。

int RecursePart(int arr[], int len, int idx, int curr_sum, int target)     
{        
    int count = 0;

    // this subset is good
    if (curr_sum == target)
       return 1;

    // the sum of the current subset exceeds target, no point in continuing
    if (curr_sum > target || idx == len)
       return 0;

    count += RecursePart(arr, len, idx+1, curr_sum + arr[idx], target);
    count += RecursePart(arr, len, idx+1, curr_sum, target);

    return count;
}

这是我之前的解决方案，它创建所有可能的子集，并计算与目标匹配的子集。

#include <iostream>

int Wrapper(int[], int, int);

int main() {
    int arr[8] = {1,2,3,4,5,6,7,8};
    std::cout << Wrapper(arr, 8, 11);
}

// counts the sum of a subset
int CountSet(int* arr, int* mask, int len)
{
    int sum = 0;

    for (int i=0; i < len; ++i)
    {
        if (mask[i])
        {
            sum += arr[i];
        }
    }
    return sum;
}


int RecursePart(int arr[], int idx, int len, int* subset_mask, int target) 
{
    int count = 0;

    if (idx == len)
    {
        if (CountSet(arr, subset_mask, len) == target)
            return 1;
        else
            return 0;
    }

    // create the subset "without" me
    subset_mask[idx] = 0;
    count += RecursePart(arr, idx+1, len, subset_mask, target);

    // now create the subset "with" me
    subset_mask[idx] = 1;
    count += RecursePart(arr, idx+1, len, subset_mask, target);

    return count;
}

int Wrapper(int arr[], int len, int target) {

    int* subset_mask = (int*)malloc(len*sizeof(int));
    int res = RecursePart(arr, 0, len, subset_mask, target);
    free(subset_mask);
    return res;
}