查找，如果possble子总和可能

Question

给定一个数组A和sum，我想找出是否存在长度K使得在序列的所有元素的总和等于给定sum的序列。

代码：

for i in(1,N): 
    for len in (i-1,0): 
     for sum in (0,Sum of all element) 
       Possible[len+1][sum] |= Possible[len][sum-A[i]] 

时间复杂度O（N^2.Sum）。有什么办法改善的时间复杂度O（N.Sum）

Answer 1

让is_subset_sum(int set[], int n, int sum)是功能查找是否存在set[]与相加等于总结的一个子集。 n是set[]中的元素数。

的is_subset_sum problem可以被划分成两个子问题

• 包含的最后一个元素，复发对于n = N-1，总和=总和 - 将[N-1]
• 排除的最后一个元素，复发对于n = n-1。

如果上述任何一个子问题返回true，则返回true。

以下是is_subset_sum（）问题的递归公式。

is_subset_sum(set, n, sum) = is_subset_sum(set, n-1, sum) || is_subset_sum(set, n-1, sum-set[n-1]) 

Base Cases: 

is_subset_sum(set, n, sum) = false, if sum > 0 and n == 0 

is_subset_sum(set, n, sum) = true, if sum == 0 

我们可以在Pseudo-polynomial time使用动态编程解决问题。我们创建一个布尔二维表子集[] []并以自下而上的方式填充它。如果存在集合[0..j-1]的子集合等于i，则子集[i] [j]的值将为真，否则为假。最后，我们返回子集Σ[n]

解的时间复杂度是O（sum * n）。

在C实现

// A Dynamic Programming solution for subset sum problem 

#include <stdio.h> 

// Returns true if there is a subset of set[] with sun equal to given sum 

bool is_subset_sum(int set[], int n, int sum) { 

    // The value of subset[i][j] will be true if there is a 

    // subset of set[0..j-1] with sum equal to i 

    bool subset[sum+1][n+1]; 

    // If sum is 0, then answer is true 

    for (int i = 0; i <= n; i++) 

     subset[0][i] = true; 

    // If sum is not 0 and set is empty, then answer is false 

    for (int i = 1; i <= sum; i++) 

     subset[i][0] = false; 

    // Fill the subset table in botton up manner 

    for (int i = 1; i <= sum; i++) { 

     for (int j = 1; j <= n; j++) { 

     subset[i][j] = subset[i][j-1]; 

     if (i >= set[j-1]) 

      subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1]; 
     } 

    } 

    /* // uncomment this code to print table 

    for (int i = 0; i <= sum; i++) { 

     for (int j = 0; j <= n; j++) 

      printf ("%4d", subset[i][j]); 

     printf("\n"); 

    } */ 

    return subset[sum][n]; 
} 

// Driver program to test above function 

int main() { 

    int set[] = {3, 34, 4, 12, 5, 2}; 

    int sum = 9; 

    int n = sizeof(set)/sizeof(set[0]); 

    if (is_subset_sum(set, n, sum) == true) 

    printf("Found a subset with given sum"); 

    else 

    printf("No subset with given sum"); 

    return 0; 
} 

Answer 2

编辑：

这可能实际上没有线性时间队列可以解决（允许的负数）。

C＃代码：

bool SubsequenceExists(int[] a, int k, int sum) 
{ 
    int currentSum = 0; 
    if (a.Length < k) return false; 

    for (int i = 0; i < a.Length; i++) 
    { 
     if (i < k) 
     { 
      currentSum += a[i]; 
      continue; 
     } 

     if (currentSum == sum) return true; 
     currentSum += a[i] - a[i-k]; 
    } 
    return false; 
} 

原来的答复：

假设你可以使用的长度K类似的东西队列应该做的工作在线性时间。

C＃代码：

bool SubsequenceExists(int[] a, int k, int sum) 
{ 
    int currentSum = 0; 
    var queue = new Queue<int>(); 

    for (int i = 0; i < a.Length; i++) 
    { 
     if (i < k) 
     { 
      queue.Enqueue(a[i]); 
      currentSum += a[i]; 
      continue; 
     } 

     if (currentSum == sum) return true; 
     currentSum -= queue.Dequeue(); 
     queue.Enqueue(a[i]); 
     currentSum += a[i]; 
    } 
    return false; 
} 

背后的逻辑非常简单：

1. 我们填充第一K元素队列中，同时存储其总和的地方。
2. 如果得到的总和不等于sum那么我们从队列中取出一个元素，并从A中添加下一个元素（同时更新总和）。
3. 我们重复第2步，直到我们到达序列的末尾或找到匹配的子序列。

Ta-daa！

Answer 3

我的功能在整个数组A上移动了一个k相邻数组项的窗口，并保持数据总和，直到它与搜索匹配失败。

int getSubSequenceStart(int A[], size_t len, int sum, size_t k) 
{  
    int sumK = 0; 

    assert(len > 0); 
    assert(k <= len); 

    // compute sum for first k items 
    for (int i = 0; i < k; i++) 
    { 
     sumK += A[i]; 
    } 

    // shift k-window upto end of A 
    for (int j = k; j < len; j++) 
    { 
     if (sumK == sum) 
     { 
      return j - k; 
     } 

     sumK += A[j] - A[j - k]; 
    } 

    return -1; 
} 

复杂性是线性与阵列A的长度。

---

更新的非连续的一般子阵列情况：
要找到一个可能的非连续的子阵，你可以从每个元素减去sum/k的A并期待将您的问题转化为subset sum problem对于总和为零的子集。已知subset sum problem的复杂性是指数级的。因此，除非数组A具有特殊属性，否则不能希望获得线性算法。