查找，如果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具有特殊屬性，否則不能希望獲得線性算法。